KMP & 拓展KMP

KMP

这个算法用来干嘛

对于一个模板串M和一个子串S,n=|M|,m=|S|。
定义tend[i]为一个最大的k使得S[1..k]=M[i-k+1..i]。
也就是说M从第i位开始往前能与S的前缀最大匹配的长度。

M= a a b b a a b a a b a
S= a a b a a b b

如上例 tend[7]=3

KMP算法就是在线性的时间复杂度内计算tend[1..n]。

算法实现

在此之前,假设我们已经计算好了一个辅助数组next[1..m]
同样的,next[i]表示一个最大的k(k<i)使得S[1..k]=S[i-k+1..i]
也就是说S自己与自己的匹配。

a a b a a b b

如上例 next[5]=2

假设我们现在要求tend[k+1],而tend[k]=p。

a a b b a a b a a b a
a a b a a b b

如上例 tend[6]=2 , 求tend[7]
如果M[k+1]=S[p+1],那么毫无疑问tend[k+1]=p+1

a a b b a a b a a b a
a a b a a b b

如上例tend[7]=3

否则呢?即如果M[k+1]≠S[p+1]

a a b b a a b a a b a
a a b a a b b

那么令p=next[p] 那么很明显依然满足M[k-p+1..k]=S[1..p]

a a b b a a b a a b a
a a b a a b b

那么如果此时M[k+1]=S[p+1],那么也毫无疑问tend[k+1]=p+1

a a b b a a b a a b a
a a b a a b b

如上例,tend[10]=6 M[10+1]≠S[6+1] 令p=next[6]=3 M[10+1]=S[3+1] 所以tend[11]=4

那么再否则呢? 细心的同学已经发现,我们可以重复上述工作,令p=next[p],直到满足S[p+1]=M[k+1]为止。 当p=0时依然不满足呢?tend[k+1]=0

哦对了,next数组应该怎样求? 难道不是一样的吗? 想象一下,如果将S串复制一份,也就是变成自己与自己的匹配,那么算法就和上述的完全一致了。

a a b a a b b
a a b a a b b

也就是说,针对上例,next[i]=tend[i]
时间复杂度:O(n+m)

扩展KMP

前言

注意与KMP的异同处,有利于理解和应用。

同样的,这个算法用来干嘛

对于一个模板串M和一个子串S,n=|M|,m=|S|
定义extend[i]为一个最大的k使得S[1..k]=M[i..i+k-1]。
也就是M以i开头的后缀与S的最长公共前缀。

M= a a b b a a b a a b a
S= a a b a a b b

如上例extned[5]=6

扩展KMP算法就是在线性的时间复杂度内计算extend[1..n]

算法实现

首先,我们假设已经计算好了一个辅助数组next[1..m]。
同样的,next[i]表示一个最大的k使得S[1..k]=S[i..i+k-1]。
也就是说S自己与自己的匹配。

a a b a a b b

如上例next[5]=1

假设我们现在要求extend[k]。
假设在此之前匹配到的最远位置为p 也就是说
假设extend[w]+w-1=p
也就是说这个最远位置就是extend[w]得来的。

a a b b a a b a a b a
a a b a a b b

如上例,我们要求假设 k=6 , 那么此时p=10 , w=5

由于M[w..p]=S[1..p-w+1] 所以M[k..p]=S[k-w+1..p-w+1]

a a b b a a b a a b a
a a b a a b b

我们令L=next[k-w+1]
那么很明显M[k..k+L-1]=S[1..L]
也就是说L是一个可行的答案

a a b b a a b a a b a
a a b a a b b

如上例,L=next[2]=1,那么M[6..6]=S[1..1]。

分两种情况:
(1)k+L-1<p
那么extend[k]=L 因为不可能再往后匹配(Why?)

用上面的例子说 我们求extend[6],p=10,w=5
由于M[5..10]=S[1..6] 所以M[6..10]=S[2..6]
令L=next[2]=1
此时k+L-1<=p 所以extend[6]=L=1

(2)k+L-1>=p
由于对于后面匹配情况的未知,我们便要往下朴素地匹配,求出extend[k]。并更新p和w

a a b b a a b a a b a
a a b a a b b

如上例,我们求extend[8],p=10,w=5

我们知道M[8..10]=S[4..6] L=next[4]=3 也就是说M[8..10]=S[1..3]

a a b b a a b a a b a
a a b a a b b

此时8+L-1>=p
所以我们继续往下匹配,求出extend[8]=4

a a b b a a b a a b a
a a b a a b b

最后一个问题
next数组怎样求。
同样的做法,不再阐述。
时间复杂度:O(n+m)

comments powered by Disqus