学步园

求一个一个串的所有前缀prefix(i)中（前缀长度为1的除外），哪些前缀可以由一个子串复制平铺K次后得到(k>1)

kmp,当求得next数组后,  另 pi = i - next[i], pi表示这个前缀prefix(i)可由长度为pi的子串平铺而成，这样，k就可由i/pi得出

#include <cstdio><br /> #define maxn 1000010<br /> char str[maxn];<br /> int next[maxn], n;<br /> void getNext() {<br /> int i = 0, j = -1;<br /> next[0] = -1;<br /> while(i < n)<br /> if(j==-1 || str[i]==str[j]) ++i, ++j, next[i] = j;<br /> else j = next[j];</p> <p>}<br /> int main () {<br /> int ca = 0;<br /> while(scanf("%d", &n), n) {<br /> scanf("%s", &str);<br /> getNext();<br /> printf("Test case #%d/n", ++ca);<br /> for(int i = 2; i <= n; ++i) {<br /> if(i-next[i] != 0 && i%(i - next[i])==0 && i/(i - next[i]) > 1)<br /> printf("%d %d/n", i, i/(i-next[i]) );<br /> }<br /> printf("/n");<br /> }<br /> return 0;<br /> }<br />