AcWing 141. 周期 || HDU 1358 Period(KMP循环节)

AcWing题目链接:https://www.acwing.com/problem/content/description/143/

HDU题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1358

子串的最小循环节就是x-Next[x],x是这个子串的长度,那么这道题我们就对字符串求一个Next数组,然后for循环扫一下每个前缀就好了。


AC代码:

#include <bits/stdc++.h>
#define maxn 1000005
#define ll long long
using namespace std;
int len;
char s[maxn];
int Next[maxn];

void init(){
	int j = 0, k = -1;
	memset(Next, -1, sizeof(Next));
	while(j < len){
		if(k == -1 || s[j] == s[k]){
				k ++;
				j ++;
				Next[j] = k;
		}
		else k = Next[k];
	}
}

int main()
{
	int Case = 1;
	while(~scanf("%d", &len)){
		if(len == 0) break;
 		scanf("%s", s);
		init();
		printf("Test case #%d\n", Case ++);
		for(int i=2;i<=len;i++){
			int xx = i - Next[i];
			if(i != xx && i % xx == 0){
				printf("%d %d\n", i, i / xx);
			}
		}
		puts("");
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券