K M P总结（上？）

[王皓宇 (小鸽子)]

话说鸽子的字符串水平真的是一坨大的

所以写篇帖子用来总结一下KMP

KMP最直接的用处就是求border（最长公共前后缀，不能是自己）

这样一个字符串的border就是xgz，同时我们发现，xg其实并不是border，那么我们就知道，border不一定会继承上一个

那么我们怎么转移呢

首先我们分析一下

一个有border字符串一定能表示为 [border] …… 和 ……[border] 的（可以相交所以不能一起说，如ababa->aba）

那么往后扩展，一定能表示为 [border'] …… + c 和 ……[border'] + c

一种情况下，能表示为 [border'] + c …… 和 ……[border'] + c ，这时候border长度加一

那么考虑border能不能多加一点

这种情况下，字符串一定能表示为 [border'] + [same] + c …… 和 ……[border] + [same] + c

这时候就有问题了，因为 border' 很明显是可以表示为 [border'] + [same] 的

所以得出border长度最多加1

---

另外考虑长度减少的

只要有border，那么它一定能表示为 [same_1] + c …… 和 ……[same_2] + c 的 (same_1 = same_2)

欸，same_1 是 border’的前缀，same_2 是border’的后缀

那么我们知道了，这个串的border一定是：它除最后一位的border（或border的border，border的border的border……可以为空）+ 最后一位字符

时间复杂度不会算，但应该是接近 O(n) 的，因为如果我的border更新时要跳很多步，那么下一位就不会走这些弯路了

关于KMP的其他事项下次还会再发一篇帖子讲的