Q - Period II

本文主要是介绍Q - Period II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Q - Period II

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

4
ooo
acmacmacmacmacma
fzufzufzuf
stostootssto

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

题意：

          求所有满足s[i]=s[i+p]的前缀的长度p；

思路:

         ls-next[xun];

 题：

        H - Seek the Name, Seek the Fame

代码：

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MM=1000005;
#define mem(a,b) memset(a,b,sizeof(a))int ne[MM],a[MM];
char mo[MM];
int lm;
void Get_next()
{int i=0,j=-1;ne[0]=-1;while(i<lm){while(j!=-1&&mo[i]!=mo[j])j=ne[j];ne[++i]=++j;}
}
int main()
{int ca,cas=1;scanf("%d",&ca);while(ca--){scanf("%s",mo);int k=0;lm=strlen(mo);a[k++]=lm;mem(ne,0);Get_next();int tmp=ne[lm];while(tmp){a[k++]=lm-tmp;tmp=ne[tmp];}printf("Case #%d: %d\n",cas++,k);for(int i=1;i<k;i++)printf("%d ",a[i]);printf("%d\n",a[0]);}return 0;
}

 

这篇关于Q - Period II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---