注明：參考文獻《資訊學奧賽一本通》
---------------------------------------------------------------------------------------------------------------------"my name is the porter of nature"
介紹
KMP演算法是用于字串匹配問題的，它利用一種巧妙而又不失邏輯的方法去減少演算法的時間復雜度，在處
理較多資料匹配時或者資料范圍大的時候用處極大（反正我是五體投地），也就是如果問主串是否包含子
串的問題可以大幅度讓你開心得飛起...
舉個栗子 ：我們有一個主串--- A=”aaaaaaaaaaaaaaaaab" 和 子串--- B=“aaab”，如果我們要找從A串中哪
一個位置起開始匹配，通常是列舉位置后驗證匹配，那么它的時間復雜度為O(n*m)[n為A串長，b為B串長]
,最壞情況下這通常不能接受，大大的TLE就給你奉上；而KMP演算法即使是最壞情況，它也可以滿足O(n)的
時間復雜度，
概念
首先我們明確幾個概念，，，
A=”aaaaaaaaaaaaaaaaab" B=“aaab”
~主串(母串)——即等待匹配的A串
~模式串——即用來匹配的B串
流程
假設我們現在有一個主串A=“abababaabab”和一個模式串B=“ababacb”，我們用實體去表示這個程序：
我們現在匹配到i=j=5時，此時前面的都可以匹配，但是A[6]!=B[6].
i= 1 2 3 4 5 6 7 8 9 ...
a b a b a b a a b a b ... (主串）
a b a b a c b (模式串）
j= 1 2 3 4 5 6 7
于是我們就用你聰明的小腦瓜子想一下，我們現在應該將j改成更小的j’,使得在B[1......j]中前面j‘個字母可以滿足剛好
和A串前面的匹配，然后繼續匹配下去，這個時候我們可以發現，B[1......j]中前面j’個字母和末尾的j'個字母
要完全相同，(如aba==aba）這樣才能移動B串，如下面所示：
i= 1 2 3 4 5 6 7 8 9 ...
a b a b a b a a b a b ... (主串）
a b a b a c b (模式串）
j= 1 2 3 4 5 6 7
這樣的話我們就可讓A[6]=B[4]了，即可以繼續匹配下去，我們也可以得知，新的j的取值與i是沒有關系
的，它就是一個B串起點在瘋狂跳躍的程序，逆向思考的話，就是在前面的j對應的字母不能匹配的話，
就縮小j，使得B串能夠跳躍去繼續匹配罷了,,
那么我們可以預處理一個陣列P[j]去處理，即它表示B組與A組匹配到B組第j個字母，第j+1個字母不能
匹配時，新的j最大可以是多少，則P[j]滿足B[1......k] = B[j-k+1......j]，(好好消化一下再繼續看）
此時我們繼續匹配下去，則有：
i= 1 2 3 4 5 6 7 8 9 ...
a b a b a b a a b a b ... (主串）
a b a b a c b (模式串）
j= 1 2 3 4 5 6 7
這時又出現A[7+1]!=B[5+1],我們就讓B開始跳起來，因為新的 j = P[5] = 3；(P的求法后續再講）
i= 1 2 3 4 5 6 7 8 9 ...
a b a b a b a a b a b ... (主串）
a b a b a c b (模式串）
j= 1 2 3 4 5 6 7
但是a != b ,所以我們 繼續 j = P[3] = 1;
i= 1 2 3 4 5 6 7 8 9 ...
a b a b a b a a b a b ... (主串）
a b a b a c b (模式串）
j= 1 2 3 4 5 6 7
依舊是不滿足，那就 j = P[1] = 0了，它已經沒力氣了~~
i= 1 2 3 4 5 6 7 8 9 ...
a b a b a b a a b a b ... (主串）
a b a b a c b (模式串）
j= 0 1 2 3 4 5 6 7
所以我們只有j==m的時候，我們才可以匹配完全...但也存在后續匹配不了滴~
先打這個匹配程序的代碼？
j=0;
for(i=0；i<sA.length();i++){
while(j>0 && sB[j+1]!=sA[i+1]) j=P[j];
//即不能繼續匹配下去，且還沒到沒力氣的時候，就繼續減小j
if(sB[j+1]==sA[i+1]) j++;
//此時可以繼續匹配，那就匹配下去
if(j==m) {
printf("%ld ",i+1-m+1);// 子串在母串的位置 ，當然是第幾個位置嘍
j=p[j]; //開啟新征程
}
}
敲黑板，劃重點
P陣列也可以用類似的方式求解，避免預處理時間復雜度達到m2--m3,但就是P陣列處理是一個自我
匹配的程序罷了，復雜度O(m)
1 2 3 4 5 6 7
B= a b a b a c b
P= 0 0 1 2 ? ? ?
此時我們不難發現，P[5] = P[4]+1; 因為由于P[4] = 2 ,則 有B [1...2] = B [ 3...4],而因為B[3] = B[5]，
所以我們就在P[4]上+1，得到P[5];
但是顯然,P[6]無法通過P[5] 得到，因為B[6]無法跟B[4]相等，那么我們或許可以繼續推下去，如果
P[P[5]]=P[3]=1可以呢，也就是說或許B[2]=B[6]呢？
然而依舊不行，所以我們就繼續下去，得到P[6]=0;
自我匹配代碼如下：
P[1]=0;
j=0;
for(long i=1;i<m;i++){
while(j>0 && B[j+1]!=B[i+1]) j=P[j];
if(B[j+1]==B[i+1]) j++;
P[i+1]=j; //將i+1位置的字符一一賦值
}
碼了2個小時，累死我了，，，
當然也要學會運用，比如刷刷題？
對了注意一點字串處理的時候，應將其從1開始
...
char B[1010];
scanf("%s",B+1);
...
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/21333.html
標籤：其他