本文主要是介绍NEFU 1318 字符串的重复周期（KMP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
字符串的重复周期
Problem:1318
Time Limit:1000ms
Memory Limit:65535K
Description
给出字符串 S，求出串S的所有前缀中，是周期串的前缀的长度 Len 和他的最大重复周期 K
Input
多组样例。 对于每组样例 第一行输入串长 N （2<=N<=1e6） 第二行输入串 S 对于所有的S，长度和小于1e7
Output
对于S中是周期串的前缀 要求输出 K>1 的前缀的长度 Len 和最大重复周期 K 每一个长度和周期用一个空格分开。
Sample Input
3 aaa 12 aabaabaabaab
Sample Output
2 2 3 3 2 2 6 2 9 3 12 4
Hint
对于第一组样例 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'
Source
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）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
