重复子串

题目链接：ybt高效进阶2-3-2

题目大意

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

思路

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

那 f a i l n fail_n failn​ 就代表着 1 ∼ f a i l n 1\sim fail_n 1∼failn​ 的子串跟 n − f a i l n + 1 ∼ n n-fail_n+1\sim n n−failn​+1∼n 的子串是相等的。

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

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

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

那如果要分成三段，就要三等分开，但是你只能从一个地方分开。
那我们考虑从哪里分开的时候相当于三等分开。

那我们要 s 1 ∼ 4 = s 5 ∼ 8 = s 9 ∼ 12 s_{1\sim4}=s_{5\sim8}=s_{9\sim12} s1∼4​=s5∼8​=s9∼12​。
那你想想两份分成了 1 ∼ a 1\sim a 1∼a 和 n − a + 1 ∼ n n-a+1\sim n n−a+1∼n，那对于一个小于等于 a a a 的正整数 b b b，会有 1 ∼ b 1\sim b 1∼b 和 n − a + 1 ∼ n − a + b n-a+1\sim n-a+b n−a+1∼n−a+b 相等。
其实，如果再有一个大于等于 b b b，小于等于 a a a 的正整数 c c c，还会有 b ∼ c b\sim c b∼c 和 n − a + b ∼ n − a + c n-a+b\sim n-a+c n−a+b∼n−a+c。

那我们可以发现，我们让长度为 8 8 8 就可以了！
相交的有四个，然后分出来的两个它们的前四个和后四个都是相等的，就刚好得出了我们要的。

那如果分成四段呢？
不难想到，就是让长度为 9 9 9。

总结一下规律，当序列长度为 n n n，你要分成 x x x 段时， f a i l n fail_n failn​ 就应该要是 n − n x n-\dfrac{n}{x} n−xn​。
（当然， n n n 一定是 x x x 的倍数，不然都分不了）

那我们看一下当 f a i l n fail_n failn​ 已经确定的时候，要分成几段。
那就是 n n − f a i l n \dfrac{n}{n-fail_n} n−failn​n​，移项可得。
当然，你也可以知道，前提是 n n n 是 n − f a i l n n-fail_n n−failn​ 的倍数，否则就只能分成一份。（就是一个整个）

代码

#include<cstdio>
#include<cstring>

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;
}