CSP-S复习计划-AC自动机

有n个单词和一句话
求出这句话包括几个单词

这就是一道例题了

很好,看了看,其他的都是套个dp,套个建图的憨憨模板,这个就好,其他自己推吧!

CSP-S复习计划-KMP

KMP

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

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

EXKMP

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

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

[NOI2014]动物园

[NOI2014]动物园
这题其实和前面有一题似乎在梦中见过的样子很像,只是这里要j*2>i时跳fail而已。

重复的子串

重复的子串
这题还是KMP裸题,但是呢我们要求出是多少次方。
因为数据保证有解,那么len\%(len-p[len])=0代表有最大重复,然后输出len/(len-p[len])就好

子串是否出现

子串是否出现
这种题目就是KMP算法的基础了,纯属考验KMP熟练程度了,没坑。
这样的话我们就匹配一下看看有没有串的长度是等于子串长度,输出一下开始结束位置就好。