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算法的精髓所在.