第2章第3節練習題2 串的模式匹配(KMP) · 數據結構與算法

## 問題描述設有主串S和子串T，子串T的定位就是要在主串S中找到一個與子串T相等的子串。 ## 算法簡述在[練習題1](http://blog.csdn.net/u013595419/article/details/50533721)中的算法是最簡單的模式匹配算法，但是該種算法每當匹配失敗時，對主串已經匹配過的字符又需要重新匹配一次，時間復雜度為O(n2)。因此這里引入了KMP算法。KMP算法與[第2章第3節練習題1 串的模式匹配(Basic) ](http://blog.csdn.net/u013595419/article/details/50533721)中算法最大的不同便是重新創建了一張跳轉表，而且使得主串僅可以訪問一次，子串可以一次跨過多個元素進行比較。為了從總體上來說明該算法，這里舉個例子：主串S：babcbabcabcaabcabcabcacabc 子串T：abcabcacab 在有些書中將子串T也稱為模式串，但這都不重要，本講解稱其為子串。首先給出經過優化后的跳轉表（next），從整體上簡單的梳理下執行過程。 - **跳轉表（next）** | j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----| | **next[j]** | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 5 | 0 | 1 | | **T[j]** | a | b | c | a | b | c | a | c | a | b | 跳轉表最大的特色就是決定了子串一次性可以跳過多少個元素與主串進行比較，跳轉表的作用是前*`next[j]-1`*個元素組成的字符串和第j號元素之前(不包括第j號元素)的*`next[j]-1`*個字符串相等，這么聽起來比較抽象，舉個簡單的例子說明下，比如以 j=8為例。當j=8時，查得next[8]=5，則可以推出前4個元素和第8號(不包括第8號元素)元素前面的4個元素相等。即：T[1]T[2]T[3]T[4]組成的字符串“abca”與T[4]T[5]T[6]T[7]組成的字符串“abcd”相等。這里簡寫為T1,2,3,4=T4,5,6,7 不失一般性，進行一次推廣，得到廣義的公式。這里令k=next[j]，即 T1,2,...,k?1==Tj?(k?1),j?(k?2),...,j?1 - **執行過程** | i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 22 | 23 | 24 | |-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----| | **S[i]** | b | a | b | c | b | a | b | c | a | b | c | a | a | b | c | a | b | c | a | b | c | a | c | a | b | c | | **T** | a | | | | | | | | | | | | | | | | | | | | | | | | | | | **T** | | a | b | c | a | | | | | | | | | | | | | | | | | | | | | | | **T** | | | | | | a | b | c | a | b | c | a | c | | | | | | | | | | | | | | | **T** | | | | | | | | | a | b | c | a | b | | | | | | | | | | | | | | | **T** | | | | | | | | | | | | | a | b | c | a | b | c | a | c | | | | | | | | **T** | | | | | | | | | | | | | | | | a | b | c | a | b | c | a | c | a | b | | 這里應該特別注意的是主串和子串的下標標號方式不同，**主串下標從0開始，子串下標從1開始**。 - 第一輪比較中，T[1]!=S[0]，查找跳轉表得`next[1]=0`此時便可以得出子串的第一個元素與此時主串的元素不匹配，對主串的下一個元素進行比較； - 進入第二輪比較，當比較到T[4]時，發現T[4]!=S[4]，查找跳轉表得`next[4]=0`，原因同上，對主串的下一個元素進行比較； - 進入第三輪比較，當比較到T[8]時，發現T[8]!=S[12]，查找跳轉表得`next[8]=5`，進入下一輪比較； - 進入第四輪比較，由上輪比較中得到`next[8]=5`，比較T[5]與S[12]，結果發現T[5]!=S[12]，查找跳轉表得`next[5]=1`，進入下輪比較； - 進入第五輪比較，由上輪比較中得到`next[5]=1`，比較T[1]與S[12]，然后發現T[1]=S[12]，開始挨個比較，比較到T[8]時，發現T[8]!=S[19]，查找跳轉表得`next[8]=5`，進入下輪比較； - 進入第六輪比較，由上輪比較中查找過程得到`next[8]=5`，比較T[5]與S[19]，結果發現T[5]=S[19]，開始逐個比較； - 最后子串T與主串S全部比較完成，返回結果。這里便可以推出KMP算法的核心執行步驟為： - 如果j==0，則表明子串的第一個元素不滿足，則將主串的下一個元素與子串的第一個元素相比； - 如果S[i]==T[j]則開始比較下一個元素，即S[i+1]與T[j+1]； - 如果不相等，則比較S[i]與T[next[j]]； ## 算法詳解在`算法簡述`中，簡單的梳理了下執行流程，也推出了KMP算法的核心步驟，與[第2章第3節練習題1 串的模式匹配(Basic) ](http://blog.csdn.net/u013595419/article/details/50533721)并無太大差異，只是如果不相等的時候，并不需要對主串S的下標重置，而是對子串T進行移位便可。而真正的難點便是建立跳轉表（next），因為滿足跳轉表（next）的元素有一個非常重要的特性便是： T1,2,...,k?1==Tj?(k?1),j?(k?2),...,j?1 而且由上面的特性很容易發現，當第j號元素與主串相應的元素“失配”時，才需要在子串中重新置位與主串再次相比，這里便引出跳轉表（next）的定義： ~~~ next[j] = ???????????0,max{k|1<k<j},1,j=1?T1,2,...,k?1==Tj?(k?1),j?(k?2),...,j?1Other ~~~ ### 思想1 那么根據上述定義，對子串T，進行分析，很容易發現定義中涉及到了子串自身的比較，即子串在求解跳轉表時既作主串又作子串，而且比較的正是T1,2,...,k?1?=Tj?(k?1),j?(k?2),...,j?1。既然這樣繼續以本文前面列出的子串T為例。 | j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----| | **T[j]** | a | b | c | a | b | c | a | c | a | b | 根據定義對子串T進行展開，可以得到下表： | j | k | = or ≠ | next[j] | |-----|-----|-----|-----| | 若 j=1 | k=0 | | next[1]=0 | | 若 j=2 | k=1 | | next[2]=1 | | 若 j=3 | k=2 | a≠b | next[3]=1 | | 若 j=4 | k=2 | a≠c | | | | k=3 | ab≠bc | next[4]=1 | | 若 j=5 | k=2 | a=a | next[5]=2 | | | k=3 | ab≠ca | | | | k=4 | abc≠bca | | | 若 j=6 | k=2 | a≠b | | | | k=3 | ab=ab | next[6]=3 | | | k=4 | abc≠cab | | | | k=5 | abca≠bcab | | | 若 j=7 | k=2 | a≠c | | | | k=3 | ab≠bc | | | | k=4 | abc=abc | next[7]=4 | | | k=5 | abca≠cabc | | | | k=6 | abcab≠bcabc | | | 若 j=8 | k=2 | a=a | | | | k=3 | ab≠ca | | | | k=4 | abc≠bca | | | | k=5 | abca=abca | next[7]=5 | | | k=6 | abcab≠cabca | | | | k=7 | abcabc≠bcabca | | | 若 j=9 | k=2 | a≠c | next[9]=1 | | | k=3 | ab≠ac | | | | k=4 | abc≠cac | | | | k=5 | abca≠bcac | | | | k=6 | abcab≠abcac | | | | k=7 | abcabc≠cabcac | | | | k=8 | abcabca≠bcabcac | | | 若 j=10 | k=2 | a=a | next[10]=2 | | | k=3 | ab≠ca | | | | k=4 | abc≠aca | | | | k=5 | abca≠caca | | | | k=6 | abcab≠bcaca | | | | k=7 | abcabc≠abcaca | | | | k=8 | abcabca≠cabcaca | | | | k=9 | abcabcac≠bcabcaca | | 整理下可得跳轉表（next） | j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----| | **next[j]** | 0 | 1 | 1 | 1 | 2 | 3 | 4 | 5 | 1 | 2 | 根據定義和上述求解過程，很容易想到用暴力方法強解此題。算法描述如下： ~~~ void BuildNext(String* T, int next[]) { int temp[MaxSize]={0}; int k,i,max; for(int j=1;j<=T->length;j++){ for(k=1;k<j;k++){ i=0; while(T->data[i]==T->data[j-k+i]&&i<k-1){ ++i; } if(i==k-1){ temp[k]=k; }else{ temp[k]=1; } } max=temp[1]; for(int cnt=1;cnt<k;cnt++){ if(max<temp[cnt]){ max=temp[cnt]; } } next[j]=max; } } ~~~ 這種解法的缺點也非常明顯，時間復雜度達到了驚人的O(n2)，這樣的算法計算跳轉表的效率明顯比較低下。 ### 思想2 跳轉表的存在的意義就是運用字符串本身的特點對下標進行置位，而滿足跳轉表條件的若干（k-1）個連續字符T1,2,...,k?1必然等于Tj?(k?1),j?(k?2),...,j?1，這樣實際上就變成了將串T既看做主串又看做子串T然后進行一次比較的過程，過程描述如下： - 主串T[2]與子串T[1]相比較，結果不相等，將next[3]置為1； - 主串T[3]與子串T[1]相比較，結果不相等，將next[4]置為1； - 主串T[4]與子串T[1]相比較，結果相等，將next[5]置為2； - 以此類推，得到next[8]=5，此時T[8]與子串T[5]，此時不相等，則不能得到next[9]； - 然后取出next[8]，使子串T[next[8]]與主串T[8]相比，結果依舊不相等；然后再取出next[5]，讓子串T[next[5]]與主串T[8]相比，結果依舊不相等；接著取出next[2]，讓子串T[next[2]]（即子串T[1]）與主串T[8]相比，結果依舊不相等；此時將next[9]置1； - 最后主串T[9]與子串T[1]相比，結果相等，則將next[10]置為2。為了更為形象的說明上面的描述，再次具體化以上過程，如下所示： | i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----| | **T** | a | b | c | a | b | c | a | c | a | b | | **T** | | a | | | | | | | | | | **T** | | | a | | | | | | | | | **T** | | | | a | b | c | a | b | | | | **T** | | | | | | | a | b | | | | **T** | | | | | | | | a | | | | **T** | | | | | | | | | a | b | 扼要的總結下思想：令k=next[j] 若T[k]==T[j]，則有T1,2,...,k==Tj?(k?1),j?(k?2),...,j；也就是說next[j+1]=next[j]+1 若T[k]！=T[j]時，便是一個回溯的過程，是求跳轉表的難點，可以參考上面的過程理解。這樣便通過將串T既看做子串又看做主串的方式進行比較，從而得到了跳轉表，如下所示： | j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----| | **next[j]** | 0 | 1 | 1 | 1 | 2 | 3 | 4 | 5 | 1 | 2 | | **T[j]** | a | b | c | a | b | c | a | c | a | b | 根據上面的過程，輕而易舉的可以寫出該算法的扼要過程，如下所示： ~~~ void BuildNext(String* T, int next[]) { int i, j; i=1; j=0; next[1]=0; while(i<T->length){ if(T->data[i]==T->data[j]||j==0){ ++i; ++j; next[i]=j; }else{ j=next[j]; } } } ~~~ 最后再將主串S和子串T從頭比較一次，熟悉下整個流程，過程如下： | i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 22 | 23 | 24 | |-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----| | **S[i]** | b | a | b | c | b | a | b | c | a | b | c | a | a | b | c | a | b | c | a | b | c | a | c | a | b | c | | **T** | a | | | | | | | | | | | | | | | | | | | | | | | | | | | **T** | | a | b | c | a | | | | | | | | | | | | | | | | | | | | | | | **T** | | | | | a | | | | | | | | | | | | | | | | | | | | | | | **T** | | | | | | a | b | c | a | b | c | a | c | | | | | | | | | | | | | | | **T** | | | | | | | | | a | b | c | a | b | | | | | | | | | | | | | | | **T** | | | | | | | | | | | | a | b | | | | | | | | | | | | | | | **T** | | | | | | | | | | | | | a | b | c | a | b | c | a | c | | | | | | | | **T** | | | | | | | | | | | | | | | | a | b | c | a | b | c | a | c | a | b | | ### 思想3 上面雖然已經完成了建立跳轉表，使用KMP算法完成了子串的查找，但是通過分析就可以發現，建立跳轉表完全可以再優化一次，即一步到位。 - 主串S[4]與子串T[4]完全可以不需要，因為T[4]==T[1]，已經判斷出T[4]!=S[4]，也就無需在額外的判斷T[1]!=S[4]了； - 主串S[12]與子串T[2]亦完全可以不要，原因同上，已知T[5]==T[2] ，也就無需判斷T[2] !=S[12]了；先對跳轉表完成優化，如下所示： - **跳轉表（next）** | j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----| | **next[j]** | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 5 | 0 | 1 | | **T[j]** | a | b | c | a | b | c | a | c | a | b | - **執行過程** | i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 22 | 23 | 24 | |-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----| | **S[i]** | b | a | b | c | b | a | b | c | a | b | c | a | a | b | c | a | b | c | a | b | c | a | c | a | b | c | | **T** | a | | | | | | | | | | | | | | | | | | | | | | | | | | | **T** | | a | b | c | a | | | | | | | | | | | | | | | | | | | | | | | **T** | | | | | | a | b | c | a | b | c | a | c | | | | | | | | | | | | | | | **T** | | | | | | | | | a | b | c | a | b | | | | | | | | | | | | | | | **T** | | | | | | | | | | | | | a | b | c | a | b | c | a | c | | | | | | | | **T** | | | | | | | | | | | | | | | | a | b | c | a | b | c | a | c | a | b | | 對上述過程進行總結，完成對算法的優化，描述如下： ~~~ void BuildNext(String* T, int next[]) { int i, j; i=1; j=0; next[1]=0; while(i<T->length){ if(T->data[i]==T->data[j]||j==0){ ++i; ++j; if(T->data[i]!=T->data[j]){ next[i]=j; }else{ next[i]=next[j]; } }else{ j=next[j]; } } } ~~~ 至此，KMP算法的講解算是完成了，具體代碼見附件。 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> #define MaxSize 100 typedef char ElemType; typedef struct{ ElemType data[MaxSize]; int length; }String; void StrCreatS(String*); void StrCreatT(String*); void Print(String*); void BuildNext(String*,int*); int KMP(String*,String*,int*); int main(int argc,char* argv[]) { String *s; s=(String*)malloc(sizeof(String)); StrCreatS(s); String *t; t=(String*)malloc(sizeof(String)); StrCreatT(t); int next[MaxSize]={0}; BuildNext(t,next); int flag=KMP(s,t,next); if(flag!=-1){ printf("Position is %d.\n",flag+1); }else{ printf("Illege Find!\n"); } return 0; } //創建主串 void StrCreatS(String* S){ char x; S->length=0; printf("Input String_S(End of '#'!):\n"); scanf("%c",&x); while(x!='#'){ S->data[S->length++]=x; scanf("%c",&x); } getchar(); } //創建子串 void StrCreatT(String* S){ char x; S->length=0; printf("Input String_T(End of '#'!):\n"); scanf("%c",&x); while(x!='#'){ S->data[++S->length]=x; scanf("%c",&x); } getchar(); } //打印字符串 void Print(String *S) { for(int i=0;i<S->length;i++){ printf("%c",S->data[i]); } printf("\n"); } //建立跳轉表 void BuildNext(String* T, int next[]) { int i, j; i=1; j=0; next[1]=0; while(i<T->length){ if(T->data[i]==T->data[j]||j==0){ ++i; ++j; if(T->data[i]!=T->data[j]){ next[i]=j; }else{ next[i]=next[j]; } }else{ j=next[j]; } } } //KMP算法的核心 int KMP(String* S, String* T,int next[]) { int i=0, j=1; while(i<S->length&&j<T->length){ if(S->data[i]==T->data[j]||j==0){ ++i; ++j; }else{ j = next[j]; } } if(j==T->length){ return i+1-T->length; }else{ return -1; } } ~~~ 參考文獻 Knuth D E, Morris J H, Pratt V R. Fast Pattern Matching in Strings.[J]. Siam Journal on Computing, 1977, 6(2):323-350. 參考Blog [http://blog.csdn.net/joylnwang/article/details/6778316](http://blog.csdn.net/joylnwang/article/details/6778316) [http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html](http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html)