KMP演算法
??首先KMP演算法是基于next函式而實作的，與BF演算法相比，KMP演算法是沒有了主串指標回溯的情況，改進后的演算法復雜度為O(m+n).KMP演算法的簡述
??每一次比較時，當子串與主串不相等的時候，主串的指標不回溯，而是通過next函式所求得的值當作下一位子串開始比較的位置，(即盡可能地向右邊滑動一段的距離，從而減少比較的次數)，
?????????? a b c a c
?? 第二趟匹配： ??a b a b c a b c a c b a b
?????????????a b c a c
?? 第三趟匹配： ??a b a b c a b c a c b a b
???????? ?????????a b c a c
??首先要解決的是，當主串和子串失配的時候子串要向后 滑動多少，這就要說到 next函式了， next函式就是計算子串每一位失配的時候應該向后滑動多少，
?? 假設此時匹配的關系如下:
????S?=?S1?S2?...?S(i-j+1)?S(i-j+2)...?S(i-k+1)?...?S(i-1)? S(i)?...?S(n)
????T?=?????????T1??T2?...??T(j-k+1)?...?T(j-1)? T(j)?...?
????T?=??????????????????T1?...?? T(k-1)? T(k)?...?
??由上圖可以看出來當 S(i)與 T(j)不相等時，從 T(j)前面的真子串開始尋找最大匹配的真前綴子串和后綴子串，若如圖所示最長的真前綴子串和后綴子串為 K-1,對比 KMP演算法示例圖，可以看出只需要 滑動使得T(k)與S(i)對齊即可，因為是最大的真前綴子串和最大的真后綴子串，所以當前子串匹配的位置前面的字符，一定與主串對應位置的各個字符相等，這樣子滑動子串就避免了主串指標的不斷回溯，
??設next[j] = k,則 next[j]表示當子串與主串失配的時候，子串下一位與主串相比的元素的下標，
??因此我們可以得到 next的函式:
??當j = 1時，說明當前處于子串的第一個有效值的位置，前面的真子串長度為0，所以next[j] = 0
??當位于其他位置的時候，next[j]的值就是目前已匹配的最長的真前綴子串的下一位，
??每一次 滑動的位數就是當前子串不匹配的位置，前面的 真前綴子串和 真后綴子串所相等時的最大子串的長度加1，
?? 實際上我們會發現子串滑動的位數與主串并沒有什么關系
int Index_KMP(SString *S, int pos, SString *T) {
int next[MAXSIZE] ;
Get_Next( T, next);
int i = pos, j = 1;
while(i <= S->len && j <= T->len) {
if(S->data[i] == T->data[j] || j == 0) {
//j == 0是一個判斷條件，當子串匹配到第一個字符的時候都沒有匹配
//子串與主串的指標都要向后移動，重新從頭開始進行匹配
++i;
++j;
} else {
j = next[j];
}
}
if(j > T->len)
return(i - T->len);
else
return 0;
}
next演算法的描述
??首先next函式是基于遞推的思想的，KMP演算法是基于next函式來實作的，
next的函式值，由上述的定義可以得到next[1] = 0,假設next[j] = k,說明最長的匹配的真前綴子串和后綴子串的長度為k-1，那么next[j+1]有以下兩種情況：
??(1)當T[j] = T[k]時，也就是說當T[j]失配的時候重新找到的匹配的位置與他相等，也就是說現在子串前k+1個字符相等，所以next[j+1]時，值為k+1，即next[j+1] = next[j] +1,一定要注意next值的定義，
??(2)當T[j] ！= T[k]時，這時候求next值的問題我們可以看作是一個模式匹配的問題，匹配的程序中模式串既是主串又是模式串，其中1<k’<k<j，相當于如果當前的失配，那么就向前一直找直到下一位與當前主串的字符相匹配，或者直到子串的第一位還是不匹配，那么主串和子串同時向后移動，這就是while回圈的條件，具體如下:
??①：若T[j] = T[k’],且k’ = next[k]，那么next[j+1] = k’+1,即next[j+1] = next[next[k]]+1.
??②：若T[j] ！= T[k]，則繼續比較T[j]和T[next[k’]]，即比較T[j]和T[next[next[k]]].
??然后一直這樣下去直到k = 0都沒有成功，則next[j+1] = 1.
void Get_Next(SString *T,int *next) {
int i = 1, j = 0;
next[1] = 0;
while(i < T->len) {
if(j == 0 || T->data[i] == T->data[j]) { //相等時，next的值等于j+1
++i;
++j;
next[i] = j;
} else {
j = next[j];//往前尋找更小的匹配的子串
}
}
}
nextval演算法的描述
??這是基于next的演算法進行的，彌補next演算法的缺陷的，
??主要解決了模式串中大量連續重復的字符，nextval函式減少了主串的無用比較的次數
??假設主串為：‘aaabaaaab’?子串為:'aaaab’則對應的next函式值為下:
??若 T[j] = T[next[j]],不需要進行S[i]和T[next[j]]的比較，直接進行S[i]和T[next[next[j]]]的比較,換句話說，此時的next[j] =next[k],將next[j]的值修正為nextval[j].
??若 T[j] != T[next[j]]的話，則當S[i] != T[j]時，還是需要進行S[i] 與 T[next[j]]的比較，因此nextval的值就是k.
void Get_NextVal(SString *T, int *next, int *nextval)
{
int j = 2;//j = 1時，nextval[1]的值默認為 0所以從2開始
nextval[1] = 0;
Get_Next( T, next);
while(j <= T->len)
{
if(T->data[j] == T->data[next[j]])
{
nextval[j] = next[next[j]];
}
else{
nextval[j] = next[j];
}
j++;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/179332.html
標籤：其他