KMP

2020-03-07

数据结构与算法

字数统计: 181字 | 阅读时长≈ 1分钟

KMP的总结

题目传送门：POJ-2406 Power Strings

题目大意：

给你一个字符串，求它的最小循环节

解题思路：

最小循环节==len/（len-next[len]）（如果能整除）

AC代码：

1	#include <cstring>
2	#include <cstdio>
3	using namespace std;
4	char a[1000005];
5	int nex[1000005];
6	int main()
7	{
8	while(scanf("%s", a) && a[0] != '.')
9	{
10	int len = strlen(a);
11	int i = 0, j = -1;
12	nex[0] = -1;
13	while(i < len)
14	{
15	if(j == -1 \|\| a[i] == a[j])
16	{
17	nex[++i] = ++j;
18	}
19	else j = nex[j];
20	}
21	if(len % (len - nex[len]) == 0)
22	printf("%d\n", len / (len - nex[len]));
23	else printf("1\n");
24	}
25	return 0;
26	}

请我喝杯咖啡吧~

支付宝

微信