算法复习之字符串(1)

（1）字符串循环左移 | 字符串全排列（递归，非递归）《本节内容》
（2）KMP算法| BF算法
（3 字符串的最长回文子串|BM算法| 字符串查找

串是有零个或者多个字符组成的有限序列，也叫字符串。电子词典查找单词就是字符串的典型应用

分清空格串和和空串；子串(子序列)和主串；串的顺序存储，链式存储；求串的长度；取第i个位置这些基础操作算法略过

一、字符串循环左移

问题：给定一个字符串S[0...N-1]，要求把S的前k 个字符移动到S的尾部，如把字符串“abcdef” 前面的2个字符‘a’、‘b’移动到字符串的尾部，得到新字符串“cdefab”:即字符串循环左移k。

• 当看到这个题目时候，必然想到暴力法，每次循环左移一位，调用K次，时间复杂度O(kN),空间复杂度O(1)

• 三次拷贝
  S[0...k] → T[0...k]
  S[k+1...N-1] → S[0...N-k-1]
  T[0...k] →S[N-k...N-1]
  时间复杂度O(N)，空间复杂度O(k)

• 上面都过于粗鲁，学过线代的都知道这个转置，可能不太恰当，理解就好，时间复杂度O(N)，空间复杂度O(1)：
  如:abcdef
  X=ab X’=ba
  Y=cdef Y’=fedc
  (X’Y’)’=(bafedc)’=cdefab
  是不是很那个奇妙，算法就是要多想想，而不是死记硬背

  void ReverseString(char*,int from,int to){
    while(from < to){
        char t = s[from];
        s[from++] = s[to];
        s[to--] = t;
    }
  }
  void leftRotateString(char*, int n, int m){
        m %= n;
        ReverseString(s,0,m-1);
        ReverseString(s,m,n-1);
        ReverseString(s,0,n-1);
  
  }
  

二、字符串全排列

问题：给定字符串S[0...N-1]，设计算法，枚举S的 全排列。

• 递归

char[] = "1234";
int size = sizeof(str) / sizeof(char);
void Permutation(int from,int to){
    if(from==to){
        for(int i = 0;i <=to;i++){
            cout<<str[i];
        }
        cout<<'\n';
        return;
    }
    for(int i = from; i<=to;i++){
        swap(str[i],str[from]);
        Permutation(from+1,to);
        swap(str[i],str[from]);
    }
} 
int _tmain(int argc, _TCHAR* argv[]){
    Permutaiton(0,size-2);
    return 0;
}

带重复字符的全排列就是每个字符分别与它后面非重复出现的字符交换。即:第i个字符与第j个字符交换时，要求[i,j)中没有与第j个字符相等的数。
代码怎么写?其实在上面基础上加上简单判断一下就行

    for(int i = from; i<=to;i++){
     if(!IsSwap(from,1))
        continue;
    swap(str[i],str[from]);
    Permutation(from+1,to);
    swap(str[i],str[from]);
    }
} 

复杂度计算：
∵f(n) = nf(n-1) + n^2
∵f (n-1)=(n-1)f(n-2) + (n-1)^2
∴f(n) = n((n-1)f(n-2) + (n-1)^2) + n^2
∵ f(n-2) = (n-2)f(n-3) + (n-2)^2
∴ f(n) = n(n-1)((n-2)f(n-3) + (n-2)^2) + n(n-1)^2 + n^2
= n(n-1)(n-2)f(n-3) + n(n-1)(n-2)^2 + n(n-1)^2 + n^2
=.......
< n! + n! + n! + n! + ... + n!
= (n+1)n!
时间复杂度为O((n+1)!)
注:当n足够大时:n! > n+1

• 非递归

步骤:后找、小大、交换、翻转——

后找:字符串中最后一个升序的位置i，即:S[k]>Sk+1，S[i]<S[i+1];
查找(小大):S[i+1...N-1]中比Ai大的最小值Sj;
交换:Si，Sj;
翻转:S[i+1...N-1]

代码就不再写了