P(j-k&＃43;1)···P(j-1)}!&＃61;NULL
1&＃xff0c; 其他情况(没有前缀与后缀或者
前缀与后缀没有相等部分)
}
什么意思&＃xff1f;
我们来演示一遍&＃xff0c;找j&＃61;4之前的子串 g go goo
next[1]&＃xff0c;因为j&＃61;1&＃xff0c;所以next[1]&＃61;0。
next[2]&＃xff0c;子串go &＃xff0c;看其前面的子串 g 的前缀与后缀的相等部分&＃xff0c;因为 g 没有前缀与后缀&＃xff0c;所以属于其他情况&＃xff0c;所以next&＃61;1。
next[3]&＃xff0c;子串goo&＃xff0c;前缀有 g go &＃xff0c;后缀 o oo&＃xff0c;
前缀与后缀没有共同部分属于其他情况&＃xff0c;所以
next[3]&＃61;1;
所以最大相似度k&＃61;1&＃xff0c;所以子串T直接移动(4-1)位。
这样节省了2步&＃xff0c;当然因为之前就已经判断过g!&＃61;d 了&＃xff0c;这里又重复了&＃xff0c;这是kMP模式匹配的缺点&＃xff0c;当然&＃xff0c;有改进版&＃xff0c;等下会说。
再来看几个例子熟悉一下next[j]函数
T&＃61;"abcabx"
它的各个子串的相似度k的值
next[1]&＃xff0c;j&＃61;1&＃xff0c;next[1]&＃61;1
next[2]&＃xff0c;a 无前缀与后缀&＃xff0c;next[2]&＃61;1
next[3]&＃xff0c;ab 前缀a与后缀b没有相等部分
next[3]&＃61;1
next[4]&＃xff0c;abc前缀a ab与后缀c bc没有相等部分
next[4]&＃61;1
next[5]&＃xff0c;abca前缀 a 与后缀 a 相等&＃xff0c;长度为1
k&＃61;相等部分长度&＃43;1&＃xff0c;所以next[5]&＃61;2
next[6]&＃xff0c;abcab&＃xff0c;前缀ab 与后缀 ab 相等
长度为2&＃xff0c;k&＃61;2&＃43;1&＃61;3&＃xff0c;next[6]&＃61;3
如何使用next[j]函数呢&＃xff1f;
比如在主串"abcdefgh"中找到该子串T"abcabx"
首先找到 j&＃61;4&＃xff0c;然后算出k&＃61;next[4]&＃61;1&＃xff0c;然后直接移动 j-k&＃61;3 步。
注意 j 的变化&＃xff0c;由4变1&＃xff0c;next[4]&＃61;1&＃xff0c;所以
next[1]函数的值就是 j 值回溯。
再来看从主串S"abcababc"中寻找子串T"abcabx"的位置。首先比较一次。
j&＃61;6&＃xff0c;next[6]&＃61;3&＃xff0c;移动(6-3)位
注意&＃xff0c;j由6变成3了 (next[6]&＃61;3)
也可以这样理解KPM模式匹配算法
求出子串T每个位置之前的前缀与后缀的最大相似度k&＃xff0c;然后与主串比较&＃xff0c;遇到第一个不相等的字符时&＃xff0c;记下其在子串T中的位置 j&＃xff0c;然后直接移动( j-next[j] )位。
由上图可知&＃xff0c;其实就是用了置换法&＃xff0c;第一次比较时&＃xff0c;该后缀已经与主串对应部分相匹配&＃xff0c;因为该前缀等于该后缀&＃xff0c;所以可以直接移动到该位置&＃xff0c;并且该公共部分无需再比较也是相等的&＃xff0c;直接从其公共部分的下一位开始比较。
KMP模式匹配算法改进版
就拿刚才所说的例子&＃xff0c;主串"goodgoogle"和
子串"google"。
按KMP模式匹配算法移动后
注意&＃xff0c;移动前的 j&＃61;4 对应的字符与移动后 j &＃61;1
的字符相等都是g&＃xff0c;并且第一次比较时已经判断了j&＃61;4的字符与主串不相等&＃xff0c;按该方法移动后则重复比较了。
也可以这样子看&＃xff1a;
按原本的KMP法&＃xff0c;移动后直接从前后缀公共部分的下一位开始比较
若移动后j1-next[j1]的 j2的字符与移动前的 j1的字符相等&＃xff0c;则又要按KMP法继续移动
j2-next[j2] ··· 直到移动前后的 j 的字符不相等为止。KMP改进法就是一步到位&＃xff0c;直接把这么多步加起来的算法也就是nextval[j]算法。
nextval[j]算法&＃xff1a;首先也需要算next[j]&＃xff0c;为了比较移动前后j位置的字符是否相等。
j&＃61;1时&＃xff0c;nextval[1]&＃61;0
后面的&＃xff1a;
若移动前后的 j 的字符不相等&＃xff0c;说明只需移动一次&＃xff0c;则nextval[j]&＃61;next[j]。
若移动前后的 j 的字符相等&＃xff0c;则说明需移动多次&＃xff0c;可以用类似于迭代法来计算&＃xff0c;
nextval[j]&＃61;nextval[next[j]]。
举个例子&＃xff1a;T串"ababaaaba"
next[j]&＃61;011234223&＃xff0c;则
nextval[1]&＃61;0
nextval[2]&＃xff1a;移动前的 j 的字符为b&＃xff0c;移动后
j&＃61;next[2]&＃61;1 的字符为a&＃xff0c;不相等&＃xff0c;
则nextval[2]&＃61;next[2]&＃61;1。
nextval[3]&＃xff1a;移动前的 j 的字符为a&＃xff0c;移动后
j&＃61;next[3]&＃61;1 的字符为a&＃xff0c;相等&＃xff0c;
则nextval[3]&＃61;nextval[next[3]]&＃61;nextval[1]&＃61;0。
nextval[4]&＃xff1a;移动前的 j 的字符为b&＃xff0c;移动后
j&＃61;next[4]&＃61;2 的字符为b&＃xff0c;相等&＃xff0c;
则nextval[4]&＃61;nextval[next[4]]&＃61;nextval[2]&＃61;1。
nextval[5]&＃xff1a;移动前的 j 的字符为a&＃xff0c;移动后
j&＃61;next[5]&＃61;3 的字符为a&＃xff0c;相等&＃xff0c;
则nextval[5]&＃61;nextval[next[5]]&＃61;nextval[3]&＃61;0。
nextval[6]&＃xff1a;移动前的 j 的字符为a&＃xff0c;移动后
j&＃61;next[6]&＃61;4 的字符为b&＃xff0c;不相等&＃xff0c;
则nextval[6]&＃61;next[6]&＃61;4。
nextval[7]&＃xff1a;移动前的 j 的字符为a&＃xff0c;移动后
j&＃61;next[7]&＃61;2 的字符为b&＃xff0c;不相等&＃xff0c;
则nextval[7]&＃61;next[7]&＃61;2。
nextval[8]&＃xff1a;移动前的 j 的字符为b&＃xff0c;移动后
j&＃61;next[8]&＃61;2 的字符为b&＃xff0c;相等&＃xff0c;
则nextval[8]&＃61;nextval[next[8]]&＃61;nextval[2]&＃61;1。
nextval[9]&＃xff1a;移动前的 j 的字符为a&＃xff0c;移动后
j&＃61;next[9]&＃61;3 的字符为a&＃xff0c;相等&＃xff0c;
则nextval[9]&＃61;nextval[next[9]]&＃61;nextval[3]&＃61;0。
所以nextval[j]&＃61;010104210
回到最初的问题&＃xff0c;"google"&＃xff0c;首先先计算它的
next[j]函数,再算nextval[j]函数&＃xff0c;然后找到第一个出现不等符号的位置 j&＃xff0c;然后直接用移动
j-nextval[j]个位置就行了。
"google"
next[j]&＃61;011121
nextval[j]&＃61;011021
第一次比较得到j&＃61;4&＃xff0c;则移动4-0&＃61;4位&＃xff0c;相当于
原KMP法执行了两次之和 3&＃43;1。
京公网安备 11010802041100号