NEFU 1318 字符串的重复周期（KMP）

本文主要是介绍NEFU 1318 字符串的重复周期（KMP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给出字符串 S，求出串S的所有前缀中，是周期串的前缀的长度 Len 和他的最大重复周期 K

多组样例。
对于每组样例
第一行输入串长 N （2<=N<=1e6）
第二行输入串 S
对于所有的S，长度和小于1e7

对于S中是周期串的前缀
要求输出 K>1 的前缀的长度 Len 和最大重复周期 K 
每一个长度和周期用一个空格分开。

3
aaa
12
aabaabaabaab

2 2
3 3
2 2
6 2
9 3
12 4

对于第一组样例 3 aaa
对于前缀 'a'   Len = 1 ，K 最大为 1 不符合要求
对于前缀 'aa'  Len = 2 ，K 最大为 2 周期串为 'a'
对于前缀 'aaa' Len = 3 ，K 最大为 3 周期串为 'a'
对于第二组样例 12 aabaabaabaab
对于前缀 'aa'  	   	 Len = 2 ，K 最大为 2 周期串为 'a'
对于前缀 'aabaab'   	 Len = 6 ，K 最大为 2 周期串为 'aab'
对于前缀 'aabaabaab'     Len = 9 ，K 最大为 3 周期串为 'aab'
对于前缀 'aabaabaabaab'  Len = 12 ，K 最大为 4 周期串为 'aab'

DT2131

思路：

用KMP求出Next数组。然后从前往后搜，对于每一个i来说，周期都为i+1-next[i]。当周期能整除长度并且前缀长度不为1的时候，那么就输出长度和最大重复周期。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char t[1000005];
int ne[1000005];
char p[1000005];
void makenext(const char p[],int ne[],int len)
{ne[0]=0;for(int i=1,k=0;i<len;i++){while(k>0&&p[i]!=p[k]) k=ne[k-1];if(p[i]==p[k]) k++;ne[i]=k;}
}
int main()
{int len;while(~scanf("%d",&len)){scanf("%s",t);makenext(t,ne,len);for(int i=0;i<len;i++){int zhouqi=i+1-ne[i];if((i+1)%zhouqi==0&&ne[i]!=0)printf("%d %d\n",i+1,(i+1)/zhouqi);}}return 0;
}

这篇关于NEFU 1318 字符串的重复周期（KMP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！