CSP-S复习计划-KMP

KMP

有a串b串,问b串在a串第一次出现的位置

就是简单的KMP模式串匹配而已,重点就是跳fail,和ac自动机原理差不多(更更更简单了)
然后就匹配就好

EXKMP

a串b串,求a[i~lena]与b的最长前缀

这题是exkmp的模板题,还是记模板好了,直接记住p,l的定义,不行就手推就好(反正打不出来就算了吧)
以下这一段都可以跳过不要问我为什么

站在k的角度看问题
定义P先后位置是k(匹配的开头位置)~i~P(匹配的结束位置)
相对应的匹配位置是 1 ~ i-k+1 ~ P-k+1k~P可以和1~P-k+1匹配,
所以说i~P可以和i-k+1 ~ P-k+1匹配
站在i-k+1的角度看问题
定义L先后位置是i-k+1(匹配的开头位置)~i-k+L(匹配的结束位置)相对应的匹配位置是1~L
整理:i-k+1 ~ P-k+1 匹配 i~P
又有:i-k+1 ~ i-k+L 匹配 1~L
因为k点最优,公共前缀较长,所以 1~L又可以匹配 i~i+L-1
分情况讨论:
如果 i-k+L<P-k+1,那么i+L-1

P-k+1,那么i+L-1>P
显然 P-k+1处于i-k+1 ~ i-k+L之中,以致i-k+1处于1~L之中 (利用整理)
那么 i-k+1 ~ P-k+1 匹配 1~P-i+1
所以 1~P-i+1 匹配 i~P
而且因为 求k的p数组时 (P-k+1)+1 和 P+1 匹配过,失败
由于第二句话显然 (P-k+1)+1=(P-i+1)+1,所以 p[i]=P-i+1
但是我们无法保证 P-i+1 大于0 因为P只和k有关。
一旦P-i+1小于0上面的推论全部没用,所以说还是得枚举。
如果 i-k+L==P-k+1
那 i-k+1 ~ P-k+1(=i-k+L) 既匹配 i~P 又匹配 1~L
因为求i-k+1的p数组时 (i-k+L)+1 和 L+1 匹配过,失败
而且因为求k的p数组时 (P-k+1)+1 和 P+1 匹配过,失败
所以 L+1 != (i-k+L)+1 P+1 != (P-k+1)+1
但无法确定 L+1 == P+1 所以就枚举吧!
最后2、3可以结合来做。

重点来了
记住这段就好

把所有代码都放了吧,没有注释了,反正被代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注