本文主要是介绍FZU Problem 1901 Period II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Problem Description
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
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
Sample Input
ooo
acmacmacmacmacma
fzufzufzuf
stostootssto
Sample Output
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 <cstdio>
#include <cstring>
const int maxn = 1000010;
int p[maxn],ans[maxn];
char str[maxn];void get_p(int len){p[1] = 0;int j = 0;for(int i = 2;i <= len;i++){while(j > 0 && str[j+1] != str[i]) j = p[j];if(str[j+1] == str[i]) j++;p[i] = j;}
}int main(){int nkase;scanf("%d",&nkase);for(int kase = 1;kase <= nkase;kase++){scanf("%s",str+1);int len = strlen(str+1);get_p(len);int t = p[len],cnt = 0;while(t){ans[cnt++] = len-t;t = p[t];}ans[cnt++] = len;printf("Case #%d: %d\n",kase,cnt);for(int i = 0;i < cnt-1;i++) printf("%d ",ans[i]);printf("%d\n",ans[cnt-1]);}return 0;
}
这篇关于FZU Problem 1901 Period II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!