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

纯属为了复习KMP,以前论文丢失了,现在参考算进重新撰写。
简单来说我们可以用O(n)的方法找到所有字串匹配原串的位置,就是基础的字符串匹配算法啦,但是如果暴力的话复杂度是O(nm)。KMP可以通过失败指针进行跳转,省去了直接暴力比对的时间。
失败指针是什么呢?就是下一个这种字串出现的位置在哪里,我们就可以在失败的时候跳去下一个可能可以继续匹配的地方继续询问,而不用暴力枚举。
那么我口胡一下KMP的过程
1. 对字串进行一次自己匹配自己的操作求出Fail数组也就是等会例题代码里面的p数组。
2. 用子串求出来的Fail值匹配母串,记录最长匹配值。
3. 在匹配值里面进行查找,如果又等于子串长度的就是有完全匹配。 ......  查看更多

重复的子串

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

子串是否出现

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