KMP模式匹配演算法
簡單的說,普通的演算法要對字串進行匹配,就要對S進行大迴圈,直到匹配成功或者全部遍歷為止。
char *S = '12351234'; char *T = '1234'; 複製程式碼
完整程式碼
#include <stdio.h> #include <string.h> int sel(char * S,char *T){ int i=0,j=0; while (i<strlen(S) && j<strlen(T)) {//迴圈開始 if (S[i]==T[j]) {//首字元對比 i++; j++; }else{ i=i-j+1;//匹配失敗,回到上次匹配的下一位 j=0;//從T的首字元和S的下一位字元再繼續匹配 } } if (j==strlen(T)) {//當j等於T的長度時說明匹配成功返回位置 return i-strlen(T)+1; } return 0; } int main() { int add=sel("12351234", "1234"); printf("%d",add); return 0; } //執行結果: 5 複製程式碼
普通演算法流程
S:12 3 5 1 2 3 4 //第一次 i=1, j=1
T:12 3 4
S: 123 5 1 2 3 4 //第二次 i=2, j=2
T: 123 4
S: 1 235 1 2 3 4 //第三次 i=3,j=3
T: 1 234
S: 1 2 351 2 3 4 //第四次失敗i=1, j=0
T: 1 2 34
...
普通演算法會無腦的迴圈匹配,其實效率是很低的,大家有沒有發現,只要匹配失敗就會從T的第i位開始從新匹配S的第一位。
S:123 5 1 2 3 4 //第一次 i=1, j=1
T:123 4
當T[0]=1, T[1]=2, S[1]=2, 顯然T[0]≠T[1], T[1]=S[1],這裡就是KMP演算法的關鍵了,去除多餘的判斷。
KMP演算法對比普通匹配演算法的優勢是:在保證i指標不回溯的前提下,當匹配失敗時,讓匹配字串向右移動最大的距離。
要保證i指標不回溯且實現功能,就只能讓j指標回溯。j指標回溯的距離,就是T字串向右移動的距離,在T中每個字元對應j指標的位置可以用演算法得出,並將得出結果存在一個數組中(陣列名為 next)。
每個匹配的字串(T),第一個對應的值為0,第二個對應的值為1。
例如:求Y(1,2,3,1,2,4,5)的next,前兩個字元對應的0和1是固定的。
第三個字元 “3” 提取字元“12”,“1”和“2”不相等,相同的個數為0,0+1=1,所以“3”對應的next是1。
第四個字元 “1” 提取字元“123”,首先“1”和“3”不想等,相同個數為0,0+1=2,所以“1” 對應的next是1。
第五個字元 “2” 提取字元“1231”,第一個“1”和最後一個“1”相同,相同個數為1,1+1=2,所以“2” 對應的next是2。
第六個字元 “4” 提取字元“12312”,前面兩個“12”和後面兩個“12”相同,相同個數為2,2+1=3,所以“4” 對應的next是3。
第七個字元 “5” 提取字元“123124”,第一個字元“1”和最後一個字元“4”不相等,相同個數為0,0+1=1,所以“5” 對應的next是1。
最終得出next陣列結果值為(0,1,1,1,2,3,1)
具體演算法如下
一
Y(下標從1開始):“1231245” next陣列(下標從1開始):01 第三個字元為“3”:由於前一個字元“2”的next的值為1,取Y[1]=“1”和“2”比較,不相等,繼續; 由於next[1]=0,結束。“3”對應的next值為1。(只要迴圈到next[1]=0,該字元的next都為1) 複製程式碼
二
Y:“1231245” next陣列:011 第四個字元為“1”:由於前一個字元“3”的next的值為1,取Y[1]=“1”和“3”比較,不相等,繼續; 由於next[1]=0,結束。“1”對應的next值為1。 複製程式碼
三
Y:“1231245” next陣列:0111 第五個字元為“2”:由於前一個字元“1”的next的值為1,取Y[1]=“1”和“1”比較,相等,1(前一個 字元“1”的next值)+1=2;“2”對應的next值為2。 複製程式碼
四
Y:“1231245” next陣列:01112 第六個字元為“4”:由於前一個字元“2”的next的值為2,取Y[2]=“2”和“2”比較,相等,2 (前一個字元“2”的next)+1=3“4”對應的next值為3。 複製程式碼
五
Y:“1231245” next陣列:011123 第七個字元為“5”:由於前一個字元“4”的next的值為3,取Y[3]=“3”和“4”比較,不相等,繼續, 由於next[3]=1,所以取Y[1]=“1”和4比較,不相等,結束;“2”對應的next值為2。 複製程式碼
最終得出next陣列結果值為(0,1,1,1,2,3,1)
演算法實現 next陣列
#include <stdio.h> #include <string.h> void Next(char*T,int *next){ int i=1; next[1]=0; int j=0; while (i<strlen(T)) { if (j==0||T[i-1]==T[j-1]) { i++; j++; next[i]=j; }else{ j=next[j]; } } } 複製程式碼
kmp演算法
int KMP(char * S,char * T){ int next[10]; Next(T,next);//根據模式串T,初始化next陣列 int i=1; int j=1; while (i<=strlen(S)&&j<=strlen(T)) { if (j==0 || S[i-1]==T[j-1]) {//如果j==0那麼表示不匹配,指標向下移動 //如果匹配成功指標也向下移動 i++; j++; } else{ j=next[j]; } } if (j>strlen(T)) { return i-(int)strlen(T); } return -1; } //主體 int main() { int i=KMP("ababcabcacbab","abcac"); printf("%d",i); return 0; } 複製程式碼
執行結果:6
優化next陣列
例如:
T: a b c a c
next 0 1 1 1 2
在T中,有兩個字元“a”,我們假設第一個為 a1,第二個為 a2。在程式匹配過程中,如果 j 指標指向 a2 時匹配失敗,那麼此時, i 指標不動,j 指標指向 a1 ,很明顯,由於 a1==a2,而 a2!=S[i],所以 a1 也肯定不等於 S[i]。
為了避免不必要的判斷,需要對 next 陣列進行精簡,對於T來說,由於 T[4] == T[next[4]] ,所以,可以將next陣列改為:
T: a b c a c
next:0 1 1 0 2 //前面說過,如果j==0那麼表示不匹配,j和i指標向下移動
void Next(char*T,int *next){ int i=1; next[1]=0; int j=0; while (i<strlen(T)) { if (j==0||T[i-1]==T[j-1]) { i++; j++; if (T[i-1]!=T[j-1]) { next[i]=j; } else{ next[i]=next[j]; } }else{ j=next[j]; } } } 複製程式碼