A POJ 3461 Oulipo

————————————————————————————————————————————
问你A字符串在B字符串中出现了几次，

只要在KMP 的过程中记录匹配到子串尾的次数就好了

B POJ 2752 Seek the Name, Seek the Fame

————————————————————————————————————————————
给你一个字符串，让你找出所有的公共前后缀，升序输出它们的长度，

公共前后缀那么就是每次找字符串结尾的NEXT值，其表示的就是它前面字符串的最长公共前后缀，
然后再对这个最长的公共前后缀重复此过程，直到找不到为止，因为找到的最长公共前后缀所能够包含母串的前后缀信息了。

实现上我们可以做一个递归，这样长度依次变小，每次里层递归结束在输出就好了。

————————————————————————————————————————————
给你一个字符串，定义字符串A*B=AB ：即 “abc”“def”=“abcdef”。问你这个字符串表示成A^x形式的时候，x的最大值

很好发现，我们要找的就是字符串的最小的那个循环节罢了。

而求这个循环节我们可以很容想到只要找到字符串的最长公共前后缀就好了，总长度减去最长公共前后缀的长度就是最小的循环节了，如果这个循环节能整除母串长度，那就可行，

如果不行那答案就是字符串本身了，也就是1.

*画一画很好想的，

————————————————————————————————————————————
给你一个字符串，问你有多少个前缀可以由一个循环节循环两次以上组成，输出每个前缀的长度和最多的循环次数

还是对每个位置找循环节就好了，

————————————————————————————————————————————
给你一个字符串，问你每个前缀在字符串中出现了多少次，输出次数和mod 10007。

显然不能枚举每个字符串来KMP。

那么我们先虑暴力对每个前缀进行KMP,然后加和就好.,复杂度是O(n^2)的,

但是我们发现的是如果对前缀ab进行KMP 那么我们找到的信息一定是包括前缀a的信息的
那么通过这一层关系我们可以统计了.

既然这是一个统计问题,那么很自然的想到了每个位置对结果的贡献.
那么每个位置对结果的贡献有
1.自己本身这个前缀,
2.这个前缀的最长的公共前后缀中后缀部分对结果的后弦和前缀贡献是一样的加上去就好了

有事最长公共前后缀,那么就是求一遍NEXT数组

然后ans[i] = ans[NEXT[i]]+1;
最后加和就好了.

————————————————————————————————————————————
给你一个字符串，问你最少添加几个字符使其能变成某个前缀循环至少2次组成的字符串。

首先如果这个字符串本身就能表示成某个前缀循环多次组成的那么就是0了
然后我们想要添加尽量少的字符，那其实也就是找循环节，方法和C题是一样的，
找到了循环节然后统计一下最后需要加几个字符就好了简单计算不再赘述。

————————————————————————————————————————————
问你母串中有多少个子串，要求子串不想交，

其实和A还是一样的只不过在匹配到子串尾的时候下一步我们让它去匹配子串头就好了

————————————————————————————————————————————
给你两个串stra，strb，让你求stra的前缀和strb的后缀的最大公共部分。

那么我们就直接将stra作为子串想strb上匹配就好了，然后最后匹配完strb，此时子串匹配的状态就是公共部分了。

————————————————————————————————————————————
据说是个EXKMP？
不做了。