本文共 862 字，大约阅读时间需要 2 分钟。

链接

题目描述

给定若干个的字符串，询问每个字符串最多是由多少个相同的子字符串重复连接而成的。

样例输入

abcdaaaaababab.

样例输出

143

思路

对于每一个字符串，我们可以用$kmp$算法，求出$p$值，则s串的第一位到第$p_n$位和$n-p_n$到第$n$位都是匹配的，那如果$n\%(n-p_n)==0$， 那就代表着存在重复子串，长度就为$n-p_n$，个数为$\frac{n}{n-p_n}$

代码

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;char s[10000005];int len, p[10000005];int main(){   	scanf("%s", s + 1);	len = strlen(s + 1);	while(len != 1 || s[1] != '.')	{   		len = strlen(s + 1);		int j = 0;		for(int i = 2; i <= len; ++i)		{   			while(j && s[i] != s[j + 1]) j = p[j];			if(s[i] == s[j + 1]) ++j;			p[i] = j;		}//KMP算法		if(len % (len - p[len]) == 0) printf("%d\n", len / (len - p[len]));//判断		else printf("1\n"); 		scanf("%s", s + 1);		len = strlen(s + 1);	}	return 0;}
      
     
    
   

转载地址：http://bbzlz.baihongyu.com/