[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熟练程度了,没坑。
这样的话我们就匹配一下看看有没有串的长度是等于子串长度,输出一下开始结束位置就好。