本文主要是介绍fzuProblem 1901 Period II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem 1901 Period II
Accept: 107 Submit: 297
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
For each prefix with length P of a given string S,if
S[i]=S[i+P] for i in [0..SIZE(S)-p-1],
then the prefix is a “period” of S. We want to all the periodic prefixs.
Input
Input contains multiple cases.
The first line contains an integer T representing the number of cases. Then following T cases.
Each test case contains a string S (1 <= SIZE(S) <= 1000000),represents the title.S consists of lowercase ,uppercase letter.
Output
For each test case, first output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of periodic prefixs.Then output the lengths of the periodic prefixs in ascending order.
Sample Input
4oooacmacmacmacmacmafzufzufzufstostootssto
Sample Output
Case #1: 3
1 2 3
Case #2: 6
3 6 9 12 15 16
Case #3: 4
3 6 9 10
Case #4: 2
9 12
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1000005;
int next[MAXN],m,cnt;
char pattern[MAXN];
int queue[MAXN],front,rear;void get_next(){int i=0, j=-1;next[i]=j;while(i<m){if(j==-1 || pattern[i]==pattern[j]){i++; j++;next[i]=j;}else j=next[j];}
}int main()
{int n;cin>>n;for(int i=1; i<=n; i++){cin>>pattern;m=strlen(pattern);get_next();front=0; rear=0; cnt=1;int t=m;while(next[t]) {queue[rear++]=next[t]; cnt++; t=next[t];}cout<<"Case #"<<i<<": "<<cnt<<endl;while(front<rear){cout<<m-queue[front++]<<" ";}cout<<m<<endl;}return 0;
}
这篇关于fzuProblem 1901 Period II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
