字符串相关算法1-字符串旋转

给你一串字符串，如何实现将将首部k个字符移动到字符串后边而不改变其他字符的顺序?

最容易想到的是，我们可以将需要移动的字符一个一个地移动到字符串的尾部。对于每次移动我们只需要一个变量记录第一个字符，后边字符往前移动就好了

这里不给出这种实现的代码。

复杂度分析：长度为n的字符串，假如需要移动m个字符到字符串末尾，那么总共需要m x n 次操作，时间复杂度为O(mn)

我们仅需要一个变量存储第一个字符位置，空间复杂度为O(1)

有没有更高效的算法呢？

基于这样的事实：一个字符串翻转两次后与原来的字符串是相同的。

因此我们可以对字符串进行这样一个操作，对需要移动的字符子串和不需要移动的字符子串分开处理:

首先对两个子串翻转一次，此时每个子串间的相对位置是不变得

然后对整个字符串再进行翻转，对于每个字符子串而言由于翻转了两次，与原来字符字串是一致的；整体进行翻转，字符子串相对位置改变一次，至此我们得到了符合要求的结果。

代码如下：

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 void RevString(char * s, int from, int to){
 5     while(from < to){
 6         swap(s[from++], s[to--]);
 7     }
 8 }
 9 void LeftRotateString(char *s, int n, int k){
10     RevString(s, 0, k - 1);
11     RevString(s, k, n - 1);
12     RevString(s, 0, n - 1);
13 }
14 int main(){
15     char s[1000];
16     int k;
17     while(cin >> s >> k){
18         LeftRotateString(s, strlen(s), k);
19         cout << s << endl;
20     }
21     return 0;
22 }

复杂度分析：长度为n的字符串，每个字符串翻转了两次，时间复杂度为O(n)