【题解】FZU-1901 Period II

Period II(FZU-1901)

题面

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 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.

输出

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.

样例输入

1
2
3
4
5
4
ooo
acmacmacmacmacma
fzufzufzuf
stostootssto

样例输出

1
2
3
4
5
6
7
8
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

提示

思路

类似【题解】POJ-2752 Seek the Name, Seek the Fame。对于字符串的所有前缀,若存在循环节,输出符合条件的前缀个数与这个前缀字符串的长度。注意输出格式,行尾不得有多余空格。

代码

查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
char t[mxn];
int nxt[mxn], ans[mxn];

void getnxt(char* t, int m)
{
int i = 0, j = -1; nxt[0] = -1;
while (i < m)
{
if (j == -1 || t[i] == t[j]) {
i++, j++;
// if (t[i] == t[j])
// nxt[i] = nxt[j]; // next数组优化
// else
nxt[i] = j;
} else
j = nxt[j];
}
}

int main()
{
int T, cs=1; scanf("%d", &T);
while(T--)
{
scanf("%s", t);
int tl = strlen(t);
getnxt(t, tl);

int num = 0;
for(int i=tl; i>0; i=nxt[i]){
ans[num++] = tl-nxt[i];
}
printf("Case #%d: %d\n", cs++, num);
for(int i=0; i<num; i++){
if(i) printf(" ");
printf("%d", ans[i]);
}
printf("\n");
}
return 0;
}
_/_/_/_/_/ EOF _/_/_/_/_/