POJ-1961 Period
Time Limit:3000MS | Memory Limit:30000K | |
Total Submissions:22012 | Accepted:10679 |
Description
Input
Output
Sample Input
3 aaa 12 aabaabaabaab 0
Sample Output
Test case #1 2 2 3 3 Test case #2 2 2 6 2 9 3 12 4
思路:和poj-2406思路相同。
#include <iostream> #include<string.h> using namespace std; const int maxn = 1e6+10; char a[maxn]; int ne[maxn]; int main() { int n; int num=0; while(scanf("%d",&n)&&n!=0) { memset(ne,0,sizeof(ne)); scanf("%s",a+1); for(int i=2,j=0;i<=n;i++) { while(j&&a[i]!=a[j+1]) j=ne[j]; if(a[i]==a[j+1]) j++; ne[i]=j; } printf("Test case #%d\n",++num); for(int i=2;i<=n;i++) { if(i%(i-ne[i])==0&&ne[i]>0) //ne[i]>0判断没有循环节的情况 { printf("%d %d\n",i,i/(i-ne[i])); } } printf("\n"); } return 0; }优质内容筛选与推荐>>