学步园

1.题意：

给定一个字符串，要求对字符串的每个位置i进行判断，判断前i个字符是否可以写成某个别的字符串的重复，若可以，求出最多可以写成多少个别的字符串的重复。比如串aabaabaab可以写成3个aab的重复

2.解法

kmp算法中next数组的应用，由于next[i]=k表示字符串a₁...a_i最多前k个字符和后k个字符对应相同，这样可以找出向前移动的字符个数L，即为最短的重复串长（循环节），重复次数为(i/i-next[i])

#include <string.h><br /> #include <iostream><br /> using namespace std;<br /> char str[1000005];<br /> int next[1000005];<br /> int len;<br /> void calc()<br /> {<br /> len=strlen(str);<br /> next[0]=-1;<br /> int i,j=-1;<br /> for (i=1;i<len;i++)<br /> {<br /> while (j!=-1&&str[j+1]!=str[i])<br /> {<br /> j=next[j];<br /> }<br /> if (str[j+1]==str[i])<br /> {<br /> j++;<br /> }<br /> next[i]=j;<br /> }<br /> }<br /> int main()<br /> {<br /> int n,t,i;<br /> t=0;<br /> while (scanf("%d",&n)!=EOF&&n)<br /> {<br /> t++;<br /> scanf("%s",&str);<br /> calc();<br /> printf("Test case #%d/n",t);<br /> for (i=1;i<len;i++)<br /> {<br /> if(next[i]!=-1&&(i+1)%(i-next[i])==0)<br /> printf("%d %d/n",i+1,(i+1)/(i-next[i]));<br /> }<br /> printf("/n");<br /> }<br /> return 0;<br /> }<br />