KMP
KMP算法可以說所有數(shù)據(jù)結(jié)構(gòu)書上都有，上大學(xué)的時(shí)候也陸陸續(xù)續(xù)學(xué)過三次，每次學(xué)完看似理解了，可是過了不到半年又忘記了，或許是因?yàn)榇a太短，能寫出來就以為自己會(huì)了，沒有深入去理解，導(dǎo)致下次再來看的時(shí)候感覺很陌生，一定是這樣的。
今天看了matrix67對(duì)KMP的解釋，很贊，附上地址：http://www.matrix67.com/blog/archives/115
為了讓老年的自己不用在遲暮的時(shí)候再學(xué)一遍KMP，還是決定把一些關(guān)鍵性的東西記錄下來，如果那時(shí)候的自己看到自己當(dāng)年寫的這篇筆記能有恍然大悟的感覺，那么現(xiàn)在就不是在浪費(fèi)時(shí)間了。
定義：
S[1... n] 目標(biāo)串 T[1...m] 模式串
算法目的：
從目標(biāo)串S中找到一個(gè)子串和模式串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) 如果不相等，則需要找到一個(gè)最大的j' < j，滿足S[i-j'...i-1]和T[1...j']完全匹配；
2) 當(dāng)i=n或j=m的時(shí)候說明匹配結(jié)束，否則重復(fù)1)；
對(duì)于j'可以這樣理解，由于前提是S[i-j...i-1]和T[1...j]完全匹配，如果要找到一個(gè)j'滿足S[i-j'...i-1]和T[1...j']也完全匹配，那么T[1...j']必定為T[1...j]的后綴，證明如下：首先將以下的子串進(jìn)行編號(hào)： A = S[i-j...i-1] B = T[1...j] C = S[i-j'...i-1] D = T[1...j']
因?yàn)锳和B完全匹配，C和D完全匹配，由于C為A的后綴，所以D為B的后綴。
當(dāng)S[i]和T[j+1]不相等的時(shí)候需要調(diào)整j的值，調(diào)整完后的j = Next[j](這個(gè)Next[j]就是之前所說的j')，需要滿足 T[1 ... Next[j] ] = = T[ j - Next[j] + 1... j ]， 并且Next[j]的值最大，比較書面的說法就是Next[j]表示在模式串T中以第j個(gè)元素為結(jié)尾的最長(zhǎng)后綴中滿足它是T的前綴的后綴的長(zhǎng)度。
舉個(gè)例子，T = "ababaaba"的Next數(shù)組為 [0, 0, 1, 2, 3, 1, 2, 3]。
由于Next數(shù)組表示的含義只和自身的性質(zhì)有關(guān)，所以在沒有目標(biāo)串的情況下同樣可以求出Next數(shù)組，KMP的精妙之處就在于求這個(gè)Next數(shù)組了。
在上文中提到的S和T的匹配中，每次S[i-j...i-1]都是盡量找到最大的j使得它和T[1...j]完全匹配，當(dāng)然有可能找不到這樣的j，此時(shí)令j = 0，即 S[i,i-1]和T[1,0]匹配(這是兩個(gè)空串，空串和空串也可以匹配，hohoho~~所以j是一定存在的)。如果現(xiàn)在把S換成T，那么問題就轉(zhuǎn)化成了T[i-j...i-1]和T[1...j]的匹配問題了，如果T[i-j...i-1]和T[1...j]完全匹配，并且T[1...j]是和T[i-j...i-1]匹配的最長(zhǎng)的串，那么 Next[i-1] 就是 j（思考一下紅色字的定義就明白了），于是問題就轉(zhuǎn)化成了T的自我匹配的過程了。
算法復(fù)雜度：
O(n+m)
Next函數(shù)的求解非常簡(jiǎn)潔：
1 #define MAXN 1000010
2 int next[MAXN];
3 4 // 傳入的字符串下標(biāo)需要以1開頭
5 void getNext(
int m,
char *str) {
6 next[1] = 0;
7 // 枚舉模式串的每個(gè)位置，判斷以當(dāng)前字符結(jié)尾能夠匹配到的最大前綴
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結(jié)尾的后綴和以j+1結(jié)尾的前綴完全匹配，j自增1。
13 if(str[i] == str[j+1]) j ++;
14 // 這里j有兩種情況：
15 // j = 0 以i結(jié)尾的后綴找不到一個(gè)前綴和它完全匹配
16 // j > 0 以i結(jié)尾的后綴和以j結(jié)尾的前綴完全匹配，更新Next函數(shù)的值
17 next[i] = j;
18 }
19 }
PKU 3461 Oulipo
題意：求一個(gè)匹配串T在目標(biāo)串S中的出現(xiàn)次數(shù)。
題解：求出T的Next數(shù)組，然后和S進(jìn)行KMP匹配，匹配時(shí)當(dāng)j = =m的時(shí)候表示找到一個(gè)可行解，計(jì)數(shù)器+1，然后將Next[j]賦值給j，使得它的最長(zhǎng)前綴能夠繼續(xù)和目標(biāo)串進(jìn)行匹配。
KMP匹配過程和Next數(shù)組的求解是一樣的。
1 // S[1n] 目標(biāo)串
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
題意：給定一個(gè)長(zhǎng)度為N(1 <= N <= 106)的字符串S，問能否和模式串EAEBE進(jìn)行匹配其中A和B表示任意隨機(jī)字符，如果能匹配，輸出E的最大可能長(zhǎng)度，不能匹配輸出0。
題解：首先利用KMP求出S的Next數(shù)組，那么S[1...Next[N]]、S[1...Next[Next[N]]]、S[1...Next[...[N]] ]必定能和S的后綴進(jìn)行完全匹配，將這些Next[i]利用一次迭代求出來，最終的答案一定在這些值中，然后從大到小枚舉這些值，判斷可行性。
假設(shè)當(dāng)前枚舉長(zhǎng)度為i，那么在S[i+1 ... N-i] 中如果能夠找到一個(gè)長(zhǎng)度為i的子串滿足和S[1...i]完全匹配，那么i就是一個(gè)可行解，又因?yàn)槊杜e是從大到小進(jìn)行的，所以i就是E可能的最大長(zhǎng)度。
于是問題就轉(zhuǎn)變成了判斷S[i+1 ... N-i]中是否存在一個(gè)和S[1...i]完全匹配的子串。如果存在，那么必定存在一個(gè)k( 2*i <= k <= N-i )，使得S[k-i+1 ... k] = = S[1 ... i ]，所以必定有Next[Next[...[k]]] = = i，所以我們可以預(yù)先將S[i+1 ... N-i]區(qū)間內(nèi)所有的Next值退化后進(jìn)行Hash，然后在枚舉某個(gè)長(zhǎng)度i的時(shí)候去Hash數(shù)組中找i是否被標(biāo)記，如果被標(biāo)記說明存在某個(gè)k滿足S[k-i+1 ... k] = = S[1 ... i ]，i就是最大可能長(zhǎng)度。
HDU 2594 Simpsons’ Hidden Talents
題意：給定兩個(gè)長(zhǎng)度不大于50000的串，求兩個(gè)串的一個(gè)最長(zhǎng)公共子串滿足子串為第一個(gè)串的前綴，并且為第二個(gè)串的后綴。
題解：將兩個(gè)串用一個(gè)從未出現(xiàn)過的字符連接，拼成一個(gè)長(zhǎng)度為N的串，然后進(jìn)行一次自我匹配，求出next數(shù)組，根據(jù)Next數(shù)組的定義，Next[N]就是所求的最大長(zhǎng)度。
HDU 3746 Cyclic Nacklace
題意：給定一個(gè)長(zhǎng)度為N(N <= 105)的字符串S，求在它的末尾添加幾個(gè)字符使得他變成一個(gè)至少重復(fù)兩次的連續(xù)重復(fù)串，要求添加的字符數(shù)最少。
題解：首先利用KMP進(jìn)行一次自我匹配求出Next數(shù)組，然后枚舉重復(fù)串的長(zhǎng)度i，令x = i * (N/i)，如果x - Next[x] == i，說明S[x]是S的一個(gè)連續(xù)重復(fù)子串（或者叫連續(xù)重復(fù)前綴更加貼切），理由很簡(jiǎn)單，將字符串S[x]以長(zhǎng)度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]，可以列出連等式，有如下等價(jià)關(guān)系：S[1...i] = = S[i+1...2i] = = ... = = S[(N/i-1)i + 1...(N/i)i]。
那么剩下的就是要看S[x+1...N]是否為S的前綴，同樣可以根據(jù)Next數(shù)組的定義進(jìn)行判斷，特殊的，當(dāng)x == N時(shí)，S[x+1...N] == S[N+1,N]為空串，必定為S的前綴，也是滿足條件的，枚舉所有滿足條件的長(zhǎng)度L，取L - (N-x)的最小者就是答案了。
PKU 2406 Power Strings
題意：給定一個(gè)長(zhǎng)度不超過N(N <= 106)的字符串，它一定是某個(gè)串重復(fù)K次得到，求這個(gè)K的最大值。
題解：假設(shè)子串T重復(fù)K次后得到串S，那么T的長(zhǎng)度一定為L(zhǎng) = N/K(要整除)，則T = S[1...L]，將S拆分成K份，每份長(zhǎng)度為L(zhǎng)，則有
S[1...L] = S[L+1...2L] = S[2L+1...3L] = ... = S[(K-1)L+1...KL]
由于要保證K最大，勢(shì)必L要取最小，所以根據(jù)Next函數(shù)的定義，有Next[KL] = (K-1)L;
即Next[N] = N - L，所以L = N - Next[N];
但是得出的長(zhǎng)度L還要保證能被N整除，所以如果不能整除說明L = N，即K = 1；而如果能整除，那么K = N / (N - Next[N]);
PKU 2752 Seek the Name, Seek the Fame
題意：給定一個(gè)長(zhǎng)度為N(N <= 400000)的字符串，求它的前綴等于后綴的所有子串的長(zhǎng)度。
題解：考察Next數(shù)組的定義。不斷迭代求N的Next，Next[N]的Next......然后逆序輸出即可。
HDU 3374 String Problem
題意：給定一個(gè)長(zhǎng)度為N(N <= 106)的字符串S，然后將它進(jìn)行左移，總共產(chǎn)生N個(gè)循環(huán)字符串，求其中字典序最小的串的編號(hào)以及這樣的串的個(gè)數(shù)，和字典序最大的串的編號(hào)以及這樣的串的個(gè)數(shù)。
題解：先求字典序最小的，字典序最大的只需要將每個(gè)字符用127減去本身再求一次字典序最小即可；定義兩個(gè)指針i，j，i初始為0，j初始為1，再定義一個(gè)長(zhǎng)度變量k = 0：
1) 比較S[i+k] 和S[j+k]的大小關(guān)系：
a) 如果相等，k自增1；當(dāng)k==N則跳出循環(huán)，否則繼續(xù)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；當(dāng)j==N或i==N則跳出循環(huán)，否則繼續(xù)1)的比較；
這樣循環(huán)結(jié)束后如果，取i和j的小者就是答案。
然后在利用求出來的下標(biāo)，生成一個(gè)新的字符串作為匹配串和一個(gè)原串的兩倍的串作為目標(biāo)串進(jìn)行KMP匹配，得到種數(shù)。
PKU 3690 Constellations題意：給定N*M(N<=1000, M <= 1000)的01矩陣S，再給定T(T <= 100)個(gè)P*Q(P <= 50, Q <= 50)的01矩陣，問P*Q的矩陣中有多少個(gè)是S的子矩陣。
題解：由于P <= 50，所以我們可以把所有P*Q的矩陣進(jìn)行二進(jìn)制位壓縮，將P*Q的矩陣的每一列壓縮成一個(gè)64位整數(shù)，這樣P*Q的矩陣就變成了一個(gè)長(zhǎng)度為Q的整數(shù)序列T，用同樣的方式對(duì)N*M的矩陣進(jìn)行壓縮，總共可以產(chǎn)生(N-P+1)個(gè)長(zhǎng)度為M的整數(shù)序列，剩下的就是進(jìn)行最多(N-P+1)次KMP匹配了。