字符串移位

给定一个字符串，要求将字符串前面m个字符移到字符串的尾部。
例如，将字符串“absdef”的前3个字符移到字符串尾部，得结果“defabc”。

法1：长度位n的字符串，移动位，共需要m*n次操作，同时设置一个变量保存第一个字符。所以，时间复杂度位O（mn），空间复杂度为O（l）；

#include<iostream>
using namespace std;

void LeftShiftOne(char *s, int n) {
    //保存左边第一个字符；
    char t = s[0];
    for (int i = 1; i < n; i++) {
        s[i - 1] = s[i];
    }
    s[n - 1] = t;
}
void LeftRotateString(char *s, int n, int m) {
    while (m--) {
        LeftShiftOne(s, n);
    }
}

int main() {

    char ch[] = "1234";
    LeftRotateString1(ch, strlen(ch), 5);
    cout << ch;
}

法2：”三步反转法”，时间复杂度O（n），空间复杂度O（l）。

    void ReverseString(char* s, int from, int to) {
    //将字符串的首尾交换
    while (from < to) {
        char t = s[from];
        s[from++] = s[to];
        s[to--] = t;
    }
}
void LeftRotateString(char* s, int n, int m) {
    //若要左移动大于n位，那么与%n是等价的
    m %= n;
    /*
    *1.将字符串分为两部分；
    *2.分别反转这两部分的字符串；
    *3.最后，将上述步骤得到的结果整体反转。
    */
    ReverseString(s, 0, m - 1);
    ReverseString(s, m, n - 1);
    ReverseString(s, 0, n - 1);
}
int main() {

    char ch[] = "1234";
    LeftRotateString(ch, strlen(ch), 5);
    cout << ch;
}