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