poj 2406 Power Strings KMP

缘起

kmp处理字符串循环节是一把好手, 来学习~ poj 2406 Power Strings

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给出一个串，问你这个最多是多少个相同的字串重复连接而成的。

【输入】
多样例. 每个样例是一个长度在[1,1000000]的字符串. 输入以 .结尾

【输出】
对每个样例,输出最多

【样例输入】
abcd
aaaa
ababab
.

【样例输出】
1
4
3

【限制】
3s

本题就是kmp的next数组的一个简单运用. 题目其实是给你一个模式串p[1,..,len], 而我们考虑 next[len+1] = k, 其实就是（根据【1】）

1
p[1,...,k-1] 和 p[len-k+2,...,len] 完全匹配, 而且保证k的最大性

那么将p向后平移sz= len-k+1的长度就能和原本的p重合. 所以如果len%sz==0的话, 则sz就是最短的周期. 答案就是 len/sz, 否则答案就是1. 特别的, k=1的时候, 虽然 sz=len len%sz==0, 但是答案也是1. 不影响的.

为什么len%sz==0的话, sz就是周期长度呢? 且看下图

其实就是一个滚雪球的过程. 上面sz就是|HB|. p1是p向右平移sz的长度. 而且p和p1重叠的部分是完全相同的（next数组的定义保证的）

p1的HB=p的BC=p1的BD=p的CE=….

这样滚雪球下去就知道p其实是以|BD|=sz为周期的字符串~ 当然，前提是len%sz==0, 如果不整除的话, 则不存在非平凡循环节（或者说整个字符串就是一个（平凡）循环节）

所以不难写下如下代码

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
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL
const int maxn = 1000005;
int len, sz, next[maxn];
char p[maxn];

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

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	while(gets(p+1), p[1]!='.') // 我的kmp板子中模式串、文本串的索引都是从1开始的
	{
		memset(next,0,sizeof(next));
		len = strlen(p+1);
		makenext();
		sz = len-next[len+1]+1;
		printf("%d\n", len%sz?1:len/sz);
	}
	return 0;
}

ac情况

Status Accepted
Time 141ms
Memory 5192kB
Length 613
Lang G++
Submitted 2019-10-23 10:00:51
Shared
RemoteRunId 20982133

参考

【1】https://yfsyfs.github.io/2019/06/17/%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%8C%B9%E9%85%8D%E7%AE%97%E6%B3%95%E4%B9%8Bkmp/