P4391 [BOI2009]Radio Transmission 无线传输
kmp
题目让我们求一个串的最小循环子串
我们回想一下kmp中的失配函数
用 f 数组保存当前字符匹配失败后，需要跳到的前一个匹配字符
而题目说主串是某个子串不断自我连接形成
那么从 子串（长度设为 i ）结束的后一个字符开始（i+1）， f 数组会递增，每次+1（可以输出看看）
到 f[ n ] 时其实就增加了 n-i 次， f[ n ]=n-i
所以答案即为 n-f[ n ]
end.
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char a[];
int n,f[];
int main(){
scanf("%d",&n); scanf("%s",a);
int j=;
for(int i=;i<n;++i){ //自我匹配
j=f[i];
while(j&&a[i]!=a[j]) j=f[j];
f[i+]= a[i]==a[j] ? j+:;
}
printf("%d",n-f[n]);
return ;
}