（1）字符串循環(huán)左移 | 字符串全排列（遞歸，非遞歸）《本節(jié)內(nèi)容》
（2）KMP算法| BF算法
（3 字符串的最長(zhǎng)回文子串|BM算法| 字符串查找

串是有零個(gè)或者多個(gè)字符組成的有限序列，也叫字符串。電子詞典查找單詞就是字符串的典型應(yīng)用

分清空格串和和空串；子串(子序列)和主串；串的順序存儲(chǔ)，鏈?zhǔn)酱鎯?chǔ)；求串的長(zhǎng)度；取第i個(gè)位置這些基礎(chǔ)操作算法略過

一、字符串循環(huán)左移

問題：給定一個(gè)字符串S[0...N-1]，要求把S的前k 個(gè)字符移動(dòng)到S的尾部，如把字符串“abcdef” 前面的2個(gè)字符‘a(chǎn)’、‘b’移動(dòng)到字符串的尾部，得到新字符串“cdefab”:即字符串循環(huán)左移k。

• 當(dāng)看到這個(gè)題目時(shí)候，必然想到暴力法，每次循環(huán)左移一位，調(diào)用K次，時(shí)間復(fù)雜度O(kN),空間復(fù)雜度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]
  時(shí)間復(fù)雜度O(N)，空間復(fù)雜度O(k)

• 上面都過于粗魯，學(xué)過線代的都知道這個(gè)轉(zhuǎn)置，可能不太恰當(dāng)，理解就好，時(shí)間復(fù)雜度O(N)，空間復(fù)雜度O(1)：
  如:abcdef
  X=ab X’=ba
  Y=cdef Y’=fedc
  (X’Y’)’=(bafedc)’=cdefab
  是不是很那個(gè)奇妙，算法就是要多想想，而不是死記硬背

  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]，設(shè)計(jì)算法，枚舉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;
}

帶重復(fù)字符的全排列就是每個(gè)字符分別與它后面非重復(fù)出現(xiàn)的字符交換。即:第i個(gè)字符與第j個(gè)字符交換時(shí)，要求[i,j)中沒有與第j個(gè)字符相等的數(shù)。
代碼怎么寫?其實(shí)在上面基礎(chǔ)上加上簡(jiǎn)單判斷一下就行

    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ù)雜度計(jì)算：
∵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!
時(shí)間復(fù)雜度為O((n+1)!)
注:當(dāng)n足夠大時(shí):n! > n+1

• 非遞歸

步驟:后找、小大、交換、翻轉(zhuǎn)——

后找:字符串中最后一個(gè)升序的位置i，即:S[k]>Sk+1，S[i]<S[i+1];
查找(小大):S[i+1...N-1]中比Ai大的最小值Sj;
交換:Si，Sj;
翻轉(zhuǎn):S[i+1...N-1]

代碼就不再寫了