字元串移位（C語言實作，面試題目）

題目：編寫程式，在原字元串中把字元串尾部的m個字元移動到字元串的頭部，要求：長度為n的字元串操作時間複雜度為O(n)，空間複雜度為O(1)。 例如，原字元串為”Ilovebaofeng”，m=7，輸出結果為：”baofengIlove”。

思路：借鑒了July的旋轉字元串的思路。分别将字元串的兩部分逆序，然後再對整個字元串逆序。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void RotateString(char *str, int from, int to);
void ShiftSubString(char* str, int m, int n);

int main()
{
	int k,len;
	char str[1000];
	printf("input a string:\n");
	scanf_s("%s", str,1000);
	len = strlen(str);
	printf("input k:\n");
	scanf_s("%d", &k);
	ShiftSubString(str, k, len);
	puts(str);
	system("pause");
	return 0;
}

void RotateString(char *str,int from, int to)
{
	char temp;
	while (from<to)
	{
		temp = str[from];
		str[from++] = str[to];
		str[to--] = temp;
	}
}
void ShiftSubString(char *str, int k, int len)
{
	RotateString(str, 0, len-k-1);
	RotateString(str, len-k, len-1);
	RotateString(str, 0, len-1 );
}
           

時間複雜度O（n），空間複雜度O（1）。