poj 1961 Period kmp求循环节

缘起

继续学习kmp求字符串循环节. poj 1961 Period

分析

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
给你一个小写字母的字符串S，长度是n, 对每个1<i<=n, 我们考察S[1,...,i]这个前缀, 我们想知道最大的
k（k>1）, 使得S[1,..,i]可以被写成某个子串A的k次幂(即A重复k次)

【输入】
多样例, 每个样例由2行构成, 第一行是n（字符串的长度, 2 <= N <= 1e6）第二行就是字符串本尊
数据集的结尾是一个0

【输出】
对每个样例, 输出存在周期的i, 以及相应的k, 每个样例结束后打印一个空行

【样例输入】
3
aaa
12
aabaabaabaab
0

【样例输出】
Test case #1
2 2
3 3

Test case #2
2 2
6 2
9 3
12 4

【限制】
3s

关于kmp解决字符串周期问题的思想在【1】中已经说过了. 知道了【1】, 本题就是水题~ 只需要求出next数组, 然后遍历i从2到n, 考虑 i%(i-next[i+1]+1), 如果==0, 而且next[i+1]>1才行. 然后打印答案就行了.

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL

const int maxn = 1000005;
int n, next[maxn];
char p[maxn];

void makenext()
{
	next[1] =0;
	for (int i = 2,k;i<=n+1; i++)
	{
		k = next[i-1];
		while(k && p[i-1]!=p[k])
		{
			k = next[k];
		}
		next[i] = k+1;
	}
}

int ck(int i)
{
	int sz = i-next[i+1]+1;
	if (next[i+1]==1 || i%sz)
	{
		return 0;
	}
	return i/sz;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	int kase = 0;
	while(scanf("%d", &n), n)
	{
		++kase;
		memset(next, 0, sizeof(next));
		scanf("%s", p+1);
		makenext();
		printf("Test case #%d\n",kase);
		for (int i = 2,k;i<=n;i++)
		{
			if (k = ck(i))
			{
				printf("%d %d\n", i, k);
			}
		}
		puts("");
	}
	return 0;
}

ac情况

Status Accepted
Time 485ms
Memory 5212kB
Length 783
Lang G++
Submitted 2019-10-23 10:30:27
Shared
RemoteRunId 20982160

参考

【1】https://yfsyfs.github.io/2019/10/23/poj-2406-Power-Strings-KMP/