KMP(1)--KMP算法解析
1. 普通字符串匹配BF算法
假設(shè)S串為原始串, T串為目標(biāo)串. 且S串匹配到i位置, T串匹配到j位置.
在BF算法中, 如果當(dāng)前字符匹配成功, (即S[i+j] == T[j]) 令j++, 繼續(xù)匹配下一個(gè)字符; 如果失配, (即S[i+j] != T[j]), 需要i++, j = 0; 也就是目標(biāo)串相對(duì)于原始串向右移動(dòng)了一位.
代碼如下 :
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; } |
對(duì)于普通的匹配算法來(lái)說(shuō), 回溯是無(wú)法避免的, 因?yàn)樗仨殞?duì)S串中的每個(gè)位置的i, 相對(duì)于T串中的j進(jìn)行檢測(cè)是否匹配. 在每次檢測(cè)的失配情況下, i的位置才會(huì)發(fā)生變化.
2. 使用KMP算法如何避免回溯
先看看下面的例子 : 第一行是S串, 第二行是T串
a | c | a | c | d | ...... |
a | c | a | c | b |
|
---> | a | c | a | c | b |
當(dāng)S串和T串在匹配到第五個(gè)字符時(shí)失配, 那么如果這時(shí)T串能夠右移2位, 那么就可以繼續(xù)下面的匹配, 如第三行所示. 同樣的道理, 如果當(dāng)T串當(dāng)前的匹配位置j失配了, 那么j可以向右移動(dòng)的值即為j的next值.
3. next數(shù)組的含義
這一部分解釋什么是next數(shù)組.
另原始串S[i], 0<=i<=n; 模式串T[i], 0<=i<=m
假設(shè)當(dāng)前的匹配情況如下 :
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], (上圖中藍(lán)色的部分為匹配的情況)那么, 我們可以當(dāng)Si和Tj失配的情況下, 讓j = j-1, 讓匹配的過(guò)程繼續(xù)下去, 這時(shí), i沒(méi)有發(fā)生改變, j的位置向左移動(dòng)了一位, 也就是說(shuō), T相對(duì)于S向右移動(dòng)了一位.
PS : 下面是重點(diǎn)哦....
也就是說(shuō), 在Si和Tj時(shí)失配的情況下. 如果要達(dá)到i不變, T串相對(duì)于S串右移的目的. 可以更新j的值, 讓T串和S串繼續(xù)匹配.
假設(shè)新的j值用next[j]表示. 如果能夠保證 :
T[j-1-next[j], j-1] == T[0, next[j]]
那么就可以讓Si和Tnext[j]繼續(xù)進(jìn)行匹配的過(guò)程. 當(dāng)然, 前提條件是next[j]<=j-1. 而next[j]即為T[0, j-1]前部分和后部分相等的長(zhǎng)度. 也就是說(shuō), next值于T串本身相關(guān)而于S串無(wú)關(guān). next數(shù)組即為KMP算法的精髓所在.