题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3670 题意：求出一个num数组一一对于字符串S的前i个字符构成的子串T，有字符串既是T的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作num[i]。求对1,000,000,007的取模 题解：不会kmp的我用exkmp做了。。求出的extend[]就是下面

Description 近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。 某天，园长给动物们讲解KMP算法。 园长：“对于一个字符串S，它的长度为L。我们可以在O(L)的时间内，求出一个名为next的数组。有谁预习了next数组的含义吗？” 熊猫：“对于字符

Description 近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。 某天，园长给动物们讲解KMP算法。 园长：“对于一个字符串S，它的长度为L。我们可以在O(L)的时间内，求出一个名为next的数组。有谁预习了next数组的含义吗？” 熊猫：“对于字符串S

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3670 题解： 以前写过一次但不是很懂，所以重新写了一下 首先构造一个cnt数组表示前缀等于后缀的子串的数目 那么cnt【i】=cnt【next【i】】+1，可以在求next同时求出来 cnt【1】=1 // 只有它本身 求 num【i】时只需找到第一个长度小于 i / 2 的子