3 aaa 12 aabaabaabaab 0
Test case #1 2 2 3 3 Test case #2 2 2 6 2 9 3 12 4 题意:求出以某一下标结尾的,循环次数大于1的前缀,输出结尾下标,循环次数。 这个题考察对kmp的next数组的理解。/* *********************************************** Author :xianxingwuguan Created Time :2014-2-2 0:56:58 File Name :2.cpp ************************************************ */ #pragma comment(linker, "/STACK:102400000,102400000") #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; const int maxn=1000100; const double pi =acos(-1.0); const double eps =1e-8; char str[maxn]; int next[maxn]; void get_next(char *str) { int i,j=0,k=-1; next[0]=-1; int len=strlen(str); while(j<len){ if(k==-1||str[j]==str[k]) next[++j]=++k; else k=next[k]; } // for(i=0;i<=len;i++)cout<<next[i]<<" ";cout<<endl; } int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); int i,j,k,m,n,count=1; while(~scanf("%d",&n)&&n) { scanf("%s",str); get_next(str); printf("Test case #%d\n",count++); for(i=1;i<=n;i++) { int ret=i-next[i]; if(i%ret==0&&i/ret>1) { printf("%d %d\n",i,i/ret); } } puts(""); } return 0; }
原文:http://blog.csdn.net/xianxingwuguan1/article/details/18892239