UVA10298:https://www.luogu.org/problemnew/show/UVA10298
思路
设P[x]数组为 前x个字符的最大前缀长度等于后缀字串
由P数组的定义我们可以知道 对于给定的长度为n字符串
则n-P[n]所在位置就是这个字符串的重复最长子串的最后一个字符的位置
如果这个字符串真的是由其中的一个子串循环而成 那么它的长度肯定是n-P[n]的倍数
因此我们用KMP预处理出给定字符串的所有P数组
再判断n是否整除n-P[n]即可 如果整除ans=n/(n-P[n])
代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 1000010
char a[maxn];
int p[maxn];
int len,j;
int main()
{
for(;;)
//死循环
{
cin>>a+
1;
//从下标1开始输入
if(a[
1]==
'.')
break;
len=strlen(a+
1);
for(
int i=
2;i<=len;i++)
//常规KMP
{
while(j&&a[j+
1]!=a[i]) j=
p[j];
if(a[j+
1]==a[i]) j++
;
p[i]=
j;
}
if(len%(len-p[len])==
0)
//如果可以整除
cout<<len/(len-p[len])<<endl;
//输出ans
else
cout<<
1<<endl;
//无解
j=
0;
//记得清0
}
}
转载于:https://www.cnblogs.com/BrokenString/p/9781566.html
相关资源：JAVA上百实例源码以及开源项目
