对扩展KMP的一些理解

对扩展KMP的一些理解

网上看了很多KMP的各种“详细”解释，“最全讲解”，“包看懂”，结果效果好像也并不是很好。。。可能是我太笨了吧

后来看了无数博客后终于有了一些自己的理解，下面我来分享一下。

假如这里有两个字符串S和T，而且要在S中寻找是否存在一段T：

现在已经找到i这个位置了，而前面最长的匹配是在po位置，匹配长度是po~p（闭区间），即S[po,p] = T[0, p-i]。
如果用extend[i] 表示S中 以i点开始的字符串 与 T 的 最大公共前缀长度的话，那么extend[po] = p-po。
如果用Next[i] 表示T中 以i点开始的字符串 与 T 的最大公共前缀长度的话，那么Next[i-po] = x 如图红色部分：

那么当匹配到i时S，T的排列应该是这样的：

且划红线部分应该是一样的：

而由于Next还记录了T的串内公共前缀，所以我们现在还知道这五个也是相同的：

这时候要分两种情况了，即 x+po 和 p 的位置关系。

• 若x+po<p
  那么很明显 以i点开始的字符串 与 T 的 最大公共前缀长度就是Next[i-po]，因为Next保证了T[x+1] != T[x]，所以S[x+po+1] != T[x+1]（这一步结合上图来看会更好理解）。

• 若x+po > p的话
  因为p已经是匹配过的最大距离了，所以p后面的都还没被匹配过，这种情况下，就要从S[i+j] 和 T[j] 开始比较了，往后枚举即可，直到找出第一个不匹配的。枚举完不要忘记更新po的值：
  

即extend[i] = j。