本来想写的更完整放题解的，但是已经有一篇了不过被埋在很下面，就大概讲下思路（

去年这道题只搞到了 84pts，最近复习字符串的时候把这道题搞出来了，但是看了眼题解用了 exkmp，我好像并不会（

题解中 Z 数组好想只是为了求每个前缀最多向后面复制多少次，但实现这个也可以简单地用 kmp 在 $O(n)$ 内实现。

实际上只要知道怎么求一个前缀的最小循环节就好了。倒序遍历整个字符串，若此时的前缀的最小循环节第一次算到，那此时的前缀就是该最小循环节最远能复制到的地方；否则最小循环节已被算到，那么就可以通过它的值算出自己的值。

代码大概如下，其中 s 为字符串数组，f 为 fail 数组，h 为每个字符串最远能向右复制几次。

for(R i=2,j=0;i<n;i++)
{
	while(j&&s[j+1]!=s[i])j=f[j];
	f[i]=j+=s[j+1]==s[i];
}
for(R i=n-1,j;i;i--)
	if(i%(j=i-f[i])==0)
	{
		int k=i/j;
		if(h[j]==1)h[j]=k;
		else if(h[i]==1)h[i]=h[j]/k;
	}