KMP演算法的實作
要求解KMP演算法，首先要得到next陣列，也有的地方叫prefix陣列，
先用手算的方法求得，
假設模式串為abacab;
第一步列出模式串的所有前綴（包括自身）：
（1）a
（2）ab
（3）aba
（4）abac
（5）abaca
（6）abacab
第二步將各個前綴看作一個獨立的字串，依次求得各個字串的最長前后綴的長度，這里的前后綴是不包括自身的（前綴不包括最后一個字符，后綴不包括第一個字符）：
具體來看第一個字串只有一個字符，因此它的前綴后綴都為空，所以它的最長公共前后綴的長度為0；
第二個字串它的最長前綴為a，最長后綴為b，無公共部分，所以最長公共前后綴的長度為0；
第三個字串最長前綴為ab，最長后綴為ba，不相等，減少前后綴的長度，前綴只剩下a，后綴也為a，因此長度為1；
第四個字串它的最長前綴為aba，最長后綴為bac，前后綴不相等，減少前后綴的長度，前綴變為ab，后綴變為ac，前后綴不相等，繼續減少前后綴的長度，前綴為a，后綴為c，不相等，所以長度為0；
五六同理，五的最長公共前后綴為a，長度為1；六的最長公共前后綴為ab，長度為2；
（1）a 0
（2）ab 0
（3）aba 1
（4）abac 0
（5）abaca 1
（6）abacab 2
求得的長度就是prefix陣列的各個元素的值；
也可以直接將prefix陣列的值全部右移一位，然后將prefix[0]的值設為-1；
下面考慮如何用代碼來實作；
先觀察第五個字串的最長前后綴長度為1，第六個字串的最長前后綴長度為2；第六個字串比第五個字串多了一個字符b，而第五個字串的的第二個字符剛好為b，所以后一個字串的長度和前一個字串是有關系的，當前一個字串的最長公共字串的長度+1的那個字符和此時的字串最后一個字符相等時，那么當前字串的長度應該是前一個字串的最長公共前后綴的長度+1，
定義兩個變數i和len；
i指向當前字串的最后一個位置；
len指向前一個字串的最長公共字串的長度+1的位置，因為陣列的下標是從0開始的；所以len的值應該為前一個字串的prefix的值+1-1，即前一個字串的prefix的值；
初始化prefix[0]=0(任何情況下都為0，因為只有一個字符時無前綴和后綴）;
i=1(指向第二個字串的最后一個位置）；
len=0；
如果p[i]==p[len]，那么len++；prefix[i]=len;(當前字串的長度比前一個字串的長度多1);
如果p[i]!=p[len]時，這也是最難理解的地方，
如圖所示，此時p[len]!=p[i],圖中的1、2部分為前面字串的最長公共前后綴，要使當前字串有公共前后綴，那么圖中的圓圈所示部分應該相等，
又因為第1,2部分的字串是相等的，所以第一部分的兩個圓圈的內容是相等的，且第一個圓圈的最后一個字符為i所指的字符，
所以當p[len]!=p[i]時，len=prefix[len-1]（len指向前一個字符的最長公共前后綴的下一個位置如圖一所示，prefix[[len-1]指向第一部分的最長公共前后綴的下一個位置，也就是第一部分第一個圓圈的最后一個位置）接下來的p[i]==p[len]的判斷會判斷第一部分第一個圓圈的最后一個位置和當前i所指的位置的值是否相等，如果相等，那么prefix[i]的值應該為第一部分的最長公共前后綴的值+1,第一部分的最長公共前后綴的長度為prefix[i-1]的值也就是當前len的值，即len++;prefix[i]=len；如果判斷p[i]==p[len]的結果為false，那么繼續在第一部分的第一個圓圈內遞回查找，比較第一個圓圈內的最長公共前后綴加一的位置和i所指的位置是否相等，說了這么多，應該不難理解了吧，下面看看代碼，
void prefix_table(char p[],int prefix[],int n){
prefix[0]=0;
int len=0;
int i=1;
while(i<n){
if(p[i]==p[len]){
len++;
prefix[i]=len;
i++;
}else{
if(len>0){/*當len=0時，len-1的值為-1，陣列下標越界*/
len=prefix[len-1];
}else{
prefix[i]=0;/*當遞回查找到第一個字符時，若果還不相等，那么這個字串的最長公共前后綴的長度肯定為0*/
i++;
}
}
}
}
將prefix陣列右移一位（kmp演算法指標回溯的位置為前一個字串的最長公共前后綴的長度所指的位置）
void move_prefix_table(int prefix[],int n){
int i;
for(i=n-1;i>0;i--){
prefix[i]=prefix[i-1];
}
prefix[0]=-1;
}
查找字串
void search(char text[],char p[]){
int n=strlen(p);
int *prefix=(int *)malloc(sizeof(int)*n);
prefix_table(p,prefix,n);
move_prefix_table(prefix,n);
int m=strlen(text);
int i,j;
while(i<m&&j<n){
if(j==-1||text[i]==p[j]){
i++;
j++;
}
else{
j=prefix[j];
}
}
if(j>n){
printf("Found\n");
}
else{
printf("Notfound\n");
}
free(prefix);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/278037.html
標籤：其他
上一篇：幾位不愿透漏姓名的優秀學長學姐出國留學經驗交流分享整理！！！！適用于大一大二大三有打算申美國學校的學弟學妹們！！！