[原创]KMP废柴のKMP小练
[原创]KMP 废柴のKMP 小练
2017-04-28 20:22:26 Tabris_ 阅读数：367
博客爬取于 2020-06-14 22:40:49
以下为正文
版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/70940766
经过 BNUCPC，发现 KMP 完全不会了，于是找几个水 KMP/NEXT 题 压压惊。
VJ 链接：https://cn.vjudge.net/contest/151711#overview
A POJ 3461 Oulipo
————————————————————————————————————————————
问你 A 字符串在 B 字符串中出现了几次，
只要在 KMP 的过程中记录匹配到子串尾的次数就好了
B POJ 2752 Seek the Name, Seek the Fame
————————————————————————————————————————————
给你一个字符串，让你找出所有的公共前后缀，升序输出它们的长度，
公共前后缀那么就是每次找字符串结尾的 NEXT 值，其表示的就是它前面字符串的最长公共前后缀，
然后再对这个最长的公共前后缀重复此过程，直到找不到为止，因为找到的最长公共前后缀所能够包含母串的前后缀信息了。
实现上我们可以做一个递归，这样长度依次变小，每次里层递归结束在输出就好了。
C POJ 2406 Power Strings
————————————————————————————————————————————
给你一个字符串，定义字符串 A*B=AB ：即 “abc”“def”=“abcdef”。问你这个字符串表示成 A^x 形式的时候，x 的最大值
很好发现，我们要找的就是字符串的最小的那个循环节罢了。
而求这个循环节我们 可以很容想到只要找到字符串的最长公共前后缀就好了，总长度减去最长公共前后缀的长度就是最小的循环节了，如果这个循环节能整除母串长度，那就可行，
如果不行那答案就是字符串本身了，也就是 1.
*画一画 很好想的，
D POJ 1961 Period
————————————————————————————————————————————
给你一个字符串，问你有多少个前缀可以由一个循环节 循环两次以上组成，输出每个前缀的长度和最多的循环次数
还是对每个位置找循环节就好了，
E HDU 3336 Count the string
————————————————————————————————————————————
给你一个字符串，问你每个前缀在字符串中出现了多少次，输出次数和 mod 10007。
显然不能枚举每个字符串来 KMP。
那么我们先虑暴力对每个前缀进行 KMP，然后加和就好。，复杂度是 O(n^2)的，
但是我们发现的是 如果对前缀 ab 进行 KMP 那么我们找到的信息一定是包括前缀 a 的信息的
那么通过这一层关系我们可以统计了。
既然这是一个统计问题，那么很自然的想到了每个位置对结果的贡献。
那么每个位置对结果的贡献有
1.自己本身这个前缀，
2.这个前缀的最长的公共前后缀中 后缀部分对结果的后弦和前缀贡献是一样的加上去就好了
有事最长公共前后缀，那么就是求一遍 NEXT 数组
然后 ans[i] = ans[NEXT[i]]+1;
最后加和就好了。
F HDU 3746 Cyclic Nacklace
————————————————————————————————————————————
给你一个字符串，问你最少添加几个字符使其能变成某个前缀循环至少 2 次组成的字符串。
首先如果这个字符串本身就能表示成某个前缀循环多次组成的那么就是 0 了
然后我们想要添加尽量少的字符，那其实也就是找循环节，方法和 C 题是一样的，
找到了循环节 然后统计一下最后需要加几个字符就好了 简单计算不再赘述。
G HDU 2087 剪花布条
————————————————————————————————————————————
问你母串中有多少个子串，要求子串不想交，
其实和 A 还是一样的只不过在匹配到子串尾的时候下一步我们让它去匹配子串头就好了
H HDU 2594 Simpsons’ Hidden Talents
————————————————————————————————————————————
给你两个串 stra，strb，让你求 stra 的前缀和 strb 的后缀的最大公共部分。
那么我们就直接将 stra 作为子串想 strb 上匹配就好了，然后最后匹配完 strb，此时子串匹配的状态就是公共部分了。
I HDU 4763 Theme Section
————————————————————————————————————————————
据说是个 EXKMP？
不做了。
