字符串循环左移

本总结是是个人为防止遗忘而作，不得转载和商用。

题目

         给定一个字符串S[0…N-1]，要求把S的前k个字符移动到S的尾部。

         如把字符串“abcdef”前面的2个字符‘a’、‘b’移动到字符串的尾部，得到新字符串“cdefab”：即字符串循环左移k。

         要求：

                   时间复杂度为 O(n)，空间复杂度为 O(1)。

分析

         直接暴力来也行，但满足不了要求，所以这里就直接说可以满足要求的算法了。

         不知道你知不知道这个：

                   假设X是个字符串，Y是个字符串，则：  (X_翻转 Y_翻转)_翻转 = YX

         如：

                   对于题目的abcdef

                   令X=ab，则X_翻转 = ba

                   令Y=cdef，则Y_翻转= fedc

                   于是(X_翻转 Y_翻转)_翻转 = (bafedc)_翻转 = cdefab

         这样就满足题目要求了。

代码

void ReverseString(char* s, int from, intto)
{
   while( from < to ){
       char t = s[from];
       s[from++] = s[to];
       s[to--] = t;
   }  
}  

void LeftRotateString(char* s, int n, intm)
{  
   // 因为循环左移n+k位和k位的效果相同，所以先k%n，然后再做运算。
    m%= m;
   ReverseString(s, 0, m - 1);
   ReverseString(s, m, n - 1);
   ReverseString(s, 0, n - 1);
}