旋转字符串问题

问题
给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前面的2个字符’a’和’b’移动到字符串的尾部，使得原字符串变成字符串“cdefab”。请写一个函数完成此功能，要求对长度为n的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。

刚开始遇到这个问题，很自然的就是想要使用一个char一个char的移动方法，也就是简称为暴力法，代码如下：

#include<iostream>
using namespace std;

void LeftShiftOne(char* ptr, int n){
    char temp = ptr[0];
    for(int i=1; i<n; i++){
        ptr[i-1] = ptr[i];
    }
    ptr[n-1] = temp;
} 

void RotateString(char *ptr, int n, int m){
    while(m--){
        LeftShiftOne(ptr, n);
    }
}

int main(){
    char s[7] = "abcdef";
    cout << s << endl;
    RotateString(s, 6, 2);
    cout << s << endl;

    return 0;
}

这种方法虽然可以解出来，但是很明显在时间复杂度上是不符合要求的，其时间复杂度为O(m*n), 因此需要考虑使用另外一种方法来解决该题。一般而言是使用三步翻转法来解决问题。

三步翻转法是先将前m个需要旋转的字符串反转一遍，即”abc”反转成为”cba”,然后将后n-m个字母反转，最后将该字符串的整体反转即可得到想要的结果，具体代码如下所示：

#include<iostream>
using namespace std;

void ReverseString(char *ptr, int from, int to){
    if(NULL == ptr || from >= to || from < 0 )
        return ;
    while(from < to){
        char temp = ptr[from];
        ptr[from++] = ptr[to];
        ptr[to--] = temp;
    }
}

void LeftRotateString(char *ptr, int n, int m){
    if(NULL == ptr || n<=0 || m>n)
        return ;
    ReverseString(ptr, 0, m-1);
    ReverseString(ptr, m, n-1);
    ReverseString(ptr, 0, n-1);
}

int main(){
    char s[7] = "abcdef";
    cout << s << endl;
    LeftRotateString(s, 6, 3);
    cout << s << endl;

    return 0;
}

至于如何证明这种方法是有效的，可以参考july在文章中的表述：https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/01.01.md

---

该题的变异题目：编写程序，在原字符串中把字符串尾部的m个字符移动到字符串的头部，要求：长度为n的字符串操作时间复杂度为O(n)，空间复杂度为O(1)。 例如，原字符串为”Ilovebaofeng”，m=7，输出结果为：”baofengIlove”。
这个题目的解法跟三步翻转法一模一样，只不过是变一下参数即可，具体不详讲，直接上代码：

void RightRotateString(char *ptr, int n, int m){
    if(NULL == ptr)
        return ;
    ReverseString(ptr, 0, n-m-1);
    ReverseString(ptr, n-m, n-1);
    ReverseString(ptr, 0, n-1);
}