??現在繼續講解KMP演算法的有關知識，以及KMP演算法的代碼和改進，改進用nextval[]陣列，
一：next公式講解
??由公式可知next[1]=0，也就是模式串第一個字符(j=1)，與主串第i個字符發生失配時，規定next[1]=0，將模式串右移一位，然后模式串第一個字符和主串的下一個位置(i+1)進行比較，
??設next[j]=k,那此時next[j+1]等于多少呢？可能有兩種情況：
1.Pk=Pj
??若Pk=Pj，則說明有最大公共前后綴，此時next[j+1]=k+1，即next[j+1]=next[j]+1，
2.Pk≠Pj
??若Pk≠Pj，則說明找到的最大公共前后綴不符合，這時可以把求next函式值的問題視為一個模式匹配的問題，如果不匹配，需要找到長度更短的相等前后綴，依次類推則一直向后尋找，尋找更小的k為k'，則next[j+1]=k'+1，也可能不存在任何k'滿足上訴條件，即不存在長度更短的相等前綴后綴，令next[j+1]=1，
??關于知道next[j]的值，計算next[j+1]的值這里已經介紹了，下面就來介紹求next值的程式，
二：求next程式
??演算法如下：
void get_next(String T,int next[]){
int i=1;j=0;
next[1] = 0;
while(i<T.length){
if(j==0!!T.ch[i]=T.ch[j]){
++i;++j;
next[i] = j; //Pi=Pj
}
else
j=next[j]; //否則令j=next[j]，回圈繼續
}
}
??用手工的方法計算的時候，比較困難，所以還是用之前的方法求next陣列，而KMP演算法就比較簡單了，根據之前得到的程序代碼如下：
int Index_KMP(String S,String T,int next[]){
int i = 1;j = 1;
while(i<=S.length&&j<=T.length){
if(j==0||S.ch[i]=S.ch[j]){
++i;++j //沒有公共前后綴或子串第一個字符比較，直接比較i+1位
}
else
j=next[j]; //模式串向右移動
}
if(j>T.length)
return i = T.length; //匹配成功
else
return 0;
}
??由上面的推斷可知，KMP演算法的時間復雜度是O(n+m)，但在一般情況下，普通模式匹配的實際執行時間近似為O(n+m)，因此至今仍被采用，KMP演算法僅在主串與子串有很多部分匹配，即最長公共前后綴時才顯得比普通演算法快得多，其主要優點是主串不回溯，
三：KMP演算法的進一步優化
??前面定義的next陣列在某些情況下尚有缺陷，還可以進一步優化，當Pj≠Sj，下次匹配應該是P(next[j])跟Sj比較，如果Pj=P(next[j])，那么相當于拿一個和Pj相等的字符跟Sj比較，這必將導致繼續失配，這樣的比較毫無意義，
??那么如何進行處理呢？就可以繼續遞回，將next[j]修正為next[next[j]]，直至兩者不相等為止，更新后的陣列命名為nextval，計算next陣列修正值的演算法如下，匹配演算法不變，只需要修改一部分，代碼如下：
void get_nextval(String T,int nextval[]){
int i=1;j=0;
nextval[1] = 0;
while(i<T.length){
if(j==0!!T.ch[i]=T.ch[j]){
++i;++j;
if(T.ch[i]!=T.ch[j])
nextval[i] = j
else
nextval[i] = nextval[j];
}
else
j=next[j];
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/140492.html
標籤：其他
上一篇：鏈表中倒數第 k 個結點