P4391 [BOI2009]Radio Transmission 无线传输——题解
刚学了KMP算法见到这道题，完全没有思路，但是真的想出来了之后，真的对KMP算法中的next数组有了更深的认识。
按照题意，读入字符串长度n和字符串ss ；
这道题求的是字符串ss最小长度的循环，我们称之为“ss的循环子串”，首先引入结论：
ans=n-next[n]
现在解释为什么答案是 n-next[n] ：
一、
先求出next数组（其实只求出next[n]就行了），即求出字符串的最大公共前后缀；
假设这两段是整个字符串ss的最大公共前后缀；
第一段： 1~next[n]
第二段： n-next[n]+1~n
为了方便观察，我将前缀和后缀分开，令它们上下一一对应；
二、 现在我们人为地把字符串按照红色段的长度划分为若干段并标号（图中的第1,2,3,4,5,6,7,8,9段）；
容易看出，红色的一段和后缀合起来就是原字符串；
所以推出：
1. 因为上下对应相等，故第1段等于红色段；
2. 因为是公共前后缀，故第2段等于第1段；
3. 因为上下对应相等，故第3段等于第2段；
4. 因为是公共前后缀，故第4段等于第3段；
5. ......
6. 红色段就是循环子串；
三、从而，我们知道了原字符串ss除去公共前后缀（图中的黑色段）中的一个剩下的就是循环子串（图中的红色段）；同样，易知原串ss除去开头（或结尾）的循环子串（图中的红色段）剩下的部分就是公共前后缀（图中的黑色段）。
至此，问题中要求的原字符串ss的最小循环子串，就转化成了求原字符串ss的最大公共前后缀；
因此，有 ans=n-next[n] 。
AC代码（kmp数组即next数组）
#include<cstdio>
using namespace std;
const int maxn=1111111;
int n,kmp[maxn];//kmp数组即next数组
char ss[maxn];
int main()
{
scanf("%d%s",&n,ss+1);
int j=0;
for(int i=2;i<=n;++i)
{
while(j&&ss[i]!=ss[j+1]) j=kmp[j];
if(ss[i]==ss[j+1]) ++j;
kmp[i]=j;
}
printf("%d",n-kmp[n]);
return 0;
}谢谢阅览