KMP算法如何理解

[zhouhaibing089]

以维基上KMP页上的例子解释:

S: ABC ABCDAB ABCDABCDABDE
P: ABCDABD

其中比较绕的部分是理解failure function, 所以我觉得可以在此尝试分享自己是如何理解的, 也许对读者有些帮助. 这一段需要细细地品.

首先我们定义一个函数f, 如果:

  p[0]=p[i-k]
  p[1]=p[i-k+1]
  ...   ...
p[k-1]=p[i-1]

换句话来讲也就是说P字符串中的前k个字符等于i前面k个字符. 我们则说: f(i)=k.

此时我们来考虑递推关系, 给定f(i)=k, 那么f(i+1)应该怎么计算呢. 可分为以下两种情况:

1. 如果此时p[k]=p[i], 按照上面定义, 我们可知f(i+1)=k+1
2. 如若不然呢, 我们检查p[i]是否等于p[f(k)].

这里是重点, 为什么是这样呢? 仍然从前提出发, f(i)=k, 意味着

(此处重复)

  p[0]=p[i-k]
  p[1]=p[i-k+1]
   ...  ...
p[k-1]=p[i-1]

f(k)表示的是:

     p[0]=p[k-f(k)]
     p[1]=p[k-f(k)+1]
       ...   ...
p[f(k)-1]=p[k-1]

结合两边, 可知:

     p[0]=p[k-f(k)]  =p[i-f(k)]
     p[1]=p[k-f(k)+1]=p[i-f(k)+1]
      ...  ...
p[f(k)-1]=p[k-1]     =p[i-1]

如果此时再有:

p[f(k)]=p[i]

则可推导出:

f(i+1)=f(k)+1

如果p[f(k)]!=p[i], 我们可以重复, 继续检查p[f(f(k))]是否等于p[i], 直至索引(index)不再有意义.

那此处以实际例子来解释: p="ABCDABD".

因为p[0]=p[0], 按照我们上面的定义:

  p[0]=p[i-k]
p[k-1]=p[i-1]

所以有i=1并且k=1, 即f(1)=1.