重复子串

解题思路

这题要处理出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;
}

谢谢