KMP(1)--KMP算法解析
1. 普通字符串匹配BF算法
假設S串為原始串, T串為目標串. 且S串匹配到i位置, T串匹配到j位置.
在BF算法中, 如果當前字符匹配成功, (即S[i+j] == T[j]) 令j++, 繼續匹配下一個字符; 如果失配, (即S[i+j] != T[j]), 需要i++, j = 0; 也就是目標串相對于原始串向右移動了一位.
代碼如下 :
int index(char* s, char* t){ int slen = strlen(s); int tlen = strlen(t);
if (slen < tlen || slen <= 0 || tlen <= 0){ return -1; }
int i = 0; ///< record position in s string int j = 0; ///< record position in t string
while (i <= slen && j <= tlen){ if (s[i + j] == t[j]){ ++j; } else{ j = 0; ++i; } } if (j == tlen){ return i; }
return -1; } |
對于普通的匹配算法來說, 回溯是無法避免的, 因為它必須對S串中的每個位置的i, 相對于T串中的j進行檢測是否匹配. 在每次檢測的失配情況下, i的位置才會發生變化.
2. 使用KMP算法如何避免回溯
先看看下面的例子 : 第一行是S串, 第二行是T串
a | c | a | c | d | ...... |
a | c | a | c | b |
|
---> | a | c | a | c | b |
當S串和T串在匹配到第五個字符時失配, 那么如果這時T串能夠右移2位, 那么就可以繼續下面的匹配, 如第三行所示. 同樣的道理, 如果當T串當前的匹配位置j失配了, 那么j可以向右移動的值即為j的next值.
3. next數組的含義
這一部分解釋什么是next數組.
另原始串S[i], 0<=i<=n; 模式串T[i], 0<=i<=m
假設當前的匹配情況如下 :
S0 | S1 | S2 | ... | Si-j | Si-j+1 | Si-j+2 | ... | Si-2 | Si-1 | Si | Si+1 | Si+2 | ... | Sn |
| T0 | T1 | T2 | ... | Tj-2 | Tj-1 | Tj | ... |
| T0 | T1 | ... | Tj-3 | Tj-2 | Tj-1 | ... |
如果S[i-j, i-1] == T[0, j-1]并且T[1, j-1] == T[0, j-2], (上圖中藍色的部分為匹配的情況)那么, 我們可以當Si和Tj失配的情況下, 讓j = j-1, 讓匹配的過程繼續下去, 這時, i沒有發生改變, j的位置向左移動了一位, 也就是說, T相對于S向右移動了一位.
PS : 下面是重點哦....
也就是說, 在Si和Tj時失配的情況下. 如果要達到i不變, T串相對于S串右移的目的. 可以更新j的值, 讓T串和S串繼續匹配.
假設新的j值用next[j]表示. 如果能夠保證 :
T[j-1-next[j], j-1] == T[0, next[j]]
那么就可以讓Si和Tnext[j]繼續進行匹配的過程. 當然, 前提條件是next[j]<=j-1. 而next[j]即為T[0, j-1]前部分和后部分相等的長度. 也就是說, next值于T串本身相關而于S串無關. next數組即為KMP算法的精髓所在.