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

重复子串

题目链接：

题目大意

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

思路

这道题我们考虑用 KMP，先对这个字符串跑一次 KMP。

那 $fai{l}_n$ 就代表着 $1\sim fai{l}_n$ 的子串跟 $n-fai{l}_n+1\sim n$ 的子串是相等的。

那我们考虑一下要在什么情况下，才会由多个相同子字符串组成。

那我们画图来看： 这个是编号，并不是字符串，我们只是要假设相等的子串的位置。

假设你要变成两段，那肯定就是从中间分开。（如下图）

那如果要分成三段，就要三等分开，但是你只能从一个地方分开。 那我们考虑从哪里分开的时候相当于三等分开。 那我们要 $s_{1\sim 4}=s_{5\sim 8}=s_{9\sim 12}$。 那你想想两份分成了 $1\sim a$ 和 $n-a+1\sim n$，那对于一个小于等于 $a$ 的正整数 $b$，会有 $1\sim b$ 和 $n-a+1\sim n-a+b$ 相等。 其实，如果再有一个大于等于 $b$，小于等于 $a$ 的正整数 $c$，还会有 $b\sim c$ 和 $n-a+b\sim n-a+c$。

那我们可以发现，我们让长度为 $8$ 就可以了！

相交的有四个，然后分出来的两个它们的前四个和后四个都是相等的，就刚好得出了我们要的。

那如果分成四段呢？

不难想到，就是让长度为 $9$。

总结一下规律，当序列长度为 $n$，你要分成 $x$ 段时，$fai{l}_n$ 就应该要是 $n-\frac{n}{x}$。

（当然，$n$ 一定是 $x$ 的倍数，不然都分不了）

那我们看一下当 $fai{l}_n$ 已经确定的时候，要分成几段。

那就是 $\frac{n}{n-fai{l}_n}$，移项可得。 当然，你也可以知道，前提是 $n$ 是 $n-fai{l}_n$ 的倍数，否则就只能分成一份。（就是一个整个）

代码

#include
   
    #include
    
     using namespace std;int an, ans, fail[1000001], j;char a[1000001];int main() {   	scanf("%s", a + 1);	an = strlen(a + 1);		while (an != 1 || a[1] != '.') {   //KMP		j = 0;		for (int i = 2; i <= an; i++) {   			while (j && a[i] != a[j + 1]) j = fail[j];			if (a[i] == a[j + 1]) j++;			fail[i] = j;		}				if (an % (an - fail[an]) == 0) printf("%d\n", an / (an - fail[an]));//可以分段			else printf("1\n");//分不了段，就只能一整个				scanf("%s", a + 1);		an = strlen(a + 1);	}		return 0;}