题目描述
n个字符的字符串，从第二个字符开始遍历。如果从第一个字符到当前字符是有循环的，那么输出当前的位置和循环次数。两组数据之间输出一个空格。
Sample Input3aaa12aabaabaabaab0
Sample OutputTest case #12 23 3
Test case #22 26 29 312 4
解题思路
假设当前是第i个字符，那么next[i+1]就是前i个字符的串里前后最大公共串，用i-next[i+1]+1就是除了前面的公共串剩下的一部分，，这一部分如果可以被(i+1)整除，就一定能够有循环节。
下面是代码
#include <cstdio>#include <cstring>const int maxn = 1000010;char s[maxn];int next[maxn];int n,kase = 0;int len;void getNext(void){memset(next,-1,sizeof(next));int k = -1;int p = 0;next[p] = k;while(p <= len-1) {if(k == -1 || s[p] == s[k]) {p++;k++;next[p] = k;}else k = next[k];}}int main(){while(scanf("%d",&n) && n) {memset(s,0,sizeof(s));scanf("%s",s);len = strlen(s);getNext();printf("Test case #%d\n",++kase);for(int i = 1 ; i < len ; i ++) {if(next[i+1] == 0) continue;int l = i+1 – next[i+1];if((i+1)%l == 0)printf("%d %d\n",i+1,(i+1)/l);}printf("\n");}return 0;}
人生难免有挫折，但你是逃避不了的，一定要去面对它
