KMP

        KMP算法可以說所有數據結構書上都有，上大學的時候也陸陸續續學過三次，每次學完看似理解了，可是過了不到半年又忘記了，或許是因為代碼太短，能寫出來就以為自己會了，沒有深入去理解，導致下次再來看的時候感覺很陌生，一定是這樣的。

    今天看了matrix67對KMP的解釋，很贊，附上地址：http://www.matrix67.com/blog/archives/115

    為了讓老年的自己不用在遲暮的時候再學一遍KMP，還是決定把一些關鍵性的東西記錄下來，如果那時候的自己看到自己當年寫的這篇筆記能有恍然大悟的感覺，那么現在就不是在浪費時間了。

      定義：

          S[1... n]   目標串                           T[1...m]   模式串

      算法目的：

          從目標串S中找到一個子串和模式串T完全匹配。

      算法核心思想：

               1) 枚舉i從1到n，在S[i-j...i-1]和T[1...j]完全匹配的前提下，判斷S[i]是否和T[j+1]相等：

                        a) 如果相等，說明S[i-j...i]和T[1...j+1]完全匹配，那么i和j都自增1；

                        b) 如果不相等，則需要找到一個最大的j' < j，滿足S[i-j'...i-1]和T[1...j']完全匹配；

               2) 當i=n或j=m的時候說明匹配結束，否則重復1)；

      對于j'可以這樣理解，由于前提是S[i-j...i-1]和T[1...j]完全匹配，如果要找到一個j'滿足S[i-j'...i-1]和T[1...j']也完全匹配，那么T[1...j']必定為T[1...j]的后綴，證明如下：首先將以下的子串進行編號： A = S[i-j...i-1]     B = T[1...j]      C = S[i-j'...i-1]     D = T[1...j']

      因為A和B完全匹配，C和D完全匹配，由于C為A的后綴，所以D為B的后綴。

      當S[i]和T[j+1]不相等的時候需要調整j的值，調整完后的j = Next[j](這個Next[j]就是之前所說的j')，需要滿足 T[1 ... Next[j] ] = = T[ j - Next[j] + 1... j ]， 并且Next[j]的值最大，比較書面的說法就是Next[j]表示在模式串T中以第j個元素為結尾的最長后綴中滿足它是T的前綴的后綴的長度。

      舉個例子，T = "ababaaba"的Next數組為 [0, 0, 1, 2, 3, 1, 2, 3]。

      由于Next數組表示的含義只和自身的性質有關，所以在沒有目標串的情況下同樣可以求出Next數組，KMP的精妙之處就在于求這個Next數組了。

      在上文中提到的S和T的匹配中，每次S[i-j...i-1]都是盡量找到最大的j使得它和T[1...j]完全匹配，當然有可能找不到這樣的j，此時令j = 0，即 S[i,i-1]和T[1,0]匹配(這是兩個空串，空串和空串也可以匹配，hohoho~~所以j是一定存在的)。如果現在把S換成T，那么問題就轉化成了T[i-j...i-1]和T[1...j]的匹配問題了，如果T[i-j...i-1]和T[1...j]完全匹配，并且T[1...j]是和T[i-j...i-1]匹配的最長的串，那么 Next[i-1] 就是 j（思考一下紅色字的定義就明白了），于是問題就轉化成了T的自我匹配的過程了。
      算法復雜度：
            O(n+m)

    Next函數的求解非常簡潔：

 1 #define MAXN 1000010
 2 int next[MAXN];
 3  
 4 // 傳入的字符串下標需要以1開頭
 5 void getNext(int m, char *str) {
 6 next[1] = 0;
 7 // 枚舉模式串的每個位置，判斷以當前字符結尾能夠匹配到的最大前綴
 8 for(int j = 0, i = 2; i <= m; i++) {
 9     // 在str[i-j i-1]和str[1j] 完全匹配的前提下判斷str[i]和str[j+1]是否相等
10     // 如果不相等，則減小j的值，直到匹配到完全相等位置
11         while( j > 0 && str[i] != str[j+1] ) j = next[j];
12         // 如果能夠找到以i結尾的后綴和以j+1結尾的前綴完全匹配，j自增1。
13         if(str[i] == str[j+1]) j ++;
14         // 這里j有兩種情況：
15         // j = 0    以i結尾的后綴找不到一個前綴和它完全匹配
16         // j > 0    以i結尾的后綴和以j結尾的前綴完全匹配，更新Next函數的值
17         next[i] = j;
18     } 
19 }

PKU 3461 Oulipo

題意：求一個匹配串T在目標串S中的出現次數。

題解：求出T的Next數組，然后和S進行KMP匹配，匹配時當j = =m的時候表示找到一個可行解，計數器+1，然后將Next[j]賦值給j，使得它的最長前綴能夠繼續和目標串進行匹配。

KMP匹配過程和Next數組的求解是一樣的。

 1 // S[1n] 目標串
 2 // T[1m] 匹配串 
 3 int KMP(int n, char *S, int m, char *T) {
 4     int cnt = 0;
 5     for(int j = 0, i = 1; i <= n; i++) {
 6         while( j>0 && S[i] != T[j+1]) j = next[j];
 7         if(S[i] == T[j+1]) j++;
 8         if(j == m) {
 9             cnt ++;
10             j = next[j];
11         }
12     }
13     return cnt;
14 }

HDU 4763 Theme Section

題意：給定一個長度為N(1 <= N <= 106)的字符串S，問能否和模式串EAEBE進行匹配其中A和B表示任意隨機字符，如果能匹配，輸出E的最大可能長度，不能匹配輸出0。

題解：首先利用KMP求出S的Next數組，那么S[1...Next[N]]、S[1...Next[Next[N]]]、S[1...Next[...[N]] ]必定能和S的后綴進行完全匹配，將這些Next[i]利用一次迭代求出來，最終的答案一定在這些值中，然后從大到小枚舉這些值，判斷可行性。

假設當前枚舉長度為i，那么在S[i+1 ... N-i] 中如果能夠找到一個長度為i的子串滿足和S[1...i]完全匹配，那么i就是一個可行解，又因為枚舉是從大到小進行的，所以i就是E可能的最大長度。

于是問題就轉變成了判斷S[i+1 ... N-i]中是否存在一個和S[1...i]完全匹配的子串。如果存在，那么必定存在一個k( 2*i <= k <= N-i )，使得S[k-i+1 ... k] = = S[1 ... i ]，所以必定有Next[Next[...[k]]] = = i，所以我們可以預先將S[i+1 ... N-i]區間內所有的Next值退化后進行Hash，然后在枚舉某個長度i的時候去Hash數組中找i是否被標記，如果被標記說明存在某個k滿足S[k-i+1 ... k] = = S[1 ... i ]，i就是最大可能長度。

HDU 2594 Simpsons’ Hidden Talents

題意：給定兩個長度不大于50000的串，求兩個串的一個最長公共子串滿足子串為第一個串的前綴，并且為第二個串的后綴。

題解：將兩個串用一個從未出現過的字符連接，拼成一個長度為N的串，然后進行一次自我匹配，求出next數組，根據Next數組的定義，Next[N]就是所求的最大長度。

HDU 3746 Cyclic Nacklace

題意：給定一個長度為N(N <= 105)的字符串S，求在它的末尾添加幾個字符使得他變成一個至少重復兩次的連續重復串，要求添加的字符數最少。

題解：首先利用KMP進行一次自我匹配求出Next數組，然后枚舉重復串的長度i，令x = i * (N/i)，如果x - Next[x] == i，說明S[x]是S的一個連續重復子串（或者叫連續重復前綴更加貼切），理由很簡單，將字符串S[x]以長度i為單位分組，

S[1...i]   S[i+1...2i]  S[2i+1...3i]   ……   S[(N/i-1)i + 1...(N/i)i]

   S[1...i]   S[i+1...2i]   ……  S[(N/i-2)i + 1...(N/i-1)i]

由于x + i = = Next[x]，可以列出連等式，有如下等價關系：S[1...i] = = S[i+1...2i] = = ... = = S[(N/i-1)i + 1...(N/i)i]。

那么剩下的就是要看S[x+1...N]是否為S的前綴，同樣可以根據Next數組的定義進行判斷，特殊的，當x == N時，S[x+1...N] == S[N+1,N]為空串，必定為S的前綴，也是滿足條件的，枚舉所有滿足條件的長度L，取L - (N-x)的最小者就是答案了。

PKU 2406 Power Strings

題意：給定一個長度不超過N(N <= 106)的字符串，它一定是某個串重復K次得到，求這個K的最大值。

題解：假設子串T重復K次后得到串S，那么T的長度一定為L = N/K(要整除)，則T = S[1...L]，將S拆分成K份，每份長度為L，則有

S[1...L] = S[L+1...2L] = S[2L+1...3L] = ... = S[(K-1)L+1...KL]

由于要保證K最大，勢必L要取最小，所以根據Next函數的定義，有Next[KL] = (K-1)L;

即Next[N] = N - L，所以L = N - Next[N];

但是得出的長度L還要保證能被N整除，所以如果不能整除說明L = N，即K = 1；而如果能整除，那么K = N / (N - Next[N]);

PKU 2752 Seek the Name, Seek the Fame

題意：給定一個長度為N(N <= 400000)的字符串，求它的前綴等于后綴的所有子串的長度。

題解：考察Next數組的定義。不斷迭代求N的Next，Next[N]的Next......然后逆序輸出即可。

HDU 3374 String Problem

題意：給定一個長度為N(N <= 106)的字符串S，然后將它進行左移，總共產生N個循環字符串，求其中字典序最小的串的編號以及這樣的串的個數，和字典序最大的串的編號以及這樣的串的個數。

題解：先求字典序最小的，字典序最大的只需要將每個字符用127減去本身再求一次字典序最小即可；定義兩個指針i，j，i初始為0，j初始為1，再定義一個長度變量k = 0：

1) 比較S[i+k] 和S[j+k]的大小關系：

a) 如果相等，k自增1；當k==N則跳出循環，否則繼續1)的比較；

b) 如果S[i+k] < S[j+k]，j += k + 1, k = 0; 

c) 如果S[i+k] > S[j+k], i += k + 1, k = 0;

2) 如果i 和j相等，j自增1；當j==N或i==N則跳出循環，否則繼續1)的比較；

這樣循環結束后如果，取i和j的小者就是答案。

然后在利用求出來的下標，生成一個新的字符串作為匹配串和一個原串的兩倍的串作為目標串進行KMP匹配，得到種數。

題意：給定N*M(N<=1000, M <= 1000)的01矩陣S，再給定T(T <= 100)個P*Q(P <= 50, Q <= 50)的01矩陣，問P*Q的矩陣中有多少個是S的子矩陣。

題解：由于P <= 50，所以我們可以把所有P*Q的矩陣進行二進制位壓縮，將P*Q的矩陣的每一列壓縮成一個64位整數，這樣P*Q的矩陣就變成了一個長度為Q的整數序列T，用同樣的方式對N*M的矩陣進行壓縮，總共可以產生(N-P+1)個長度為M的整數序列，剩下的就是進行最多(N-P+1)次KMP匹配了。