重复子串
解题思路
这题要处理出next数组(前i个字符中,最长相同前缀后缀)
设len为字符串s的长度
就是字符串第一位到next[len]位与len-next[len]位到第len位是匹配的
所以len%(len-next[len])为0时
就存在重复连续子串
长度为len-next[len]
循环次数为len/(len-next[len])
否则为1
AC代码
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char s[1000005];
int len,next[1000005];
int main()
{
scanf("%s",s+1);
while(s[1]!='.')//多组数据
{
len=strlen(s+1);//长度
next[0]=0;//初值
for(int i=2,k=0;i<=len;i++)//求next数组
{
while(k&&s[i]!=s[k+1]) k=next[k];//不等
if(s[i]==s[k+1]) k++;//相等
next[i]=k;//赋值
}
if(len%(len-next[len])==0)printf("%d\n",len/(len-next[len]));//判断
else printf("1\n");
scanf("%s",s+1);
}
return 0;
}