本文主要是介绍uvalive3026（kmp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
大白书上面的例题，不过真的不是很好理解，首先假设0到i是一个循环串，那么i-f[i]一定是一个最小正周期，其中f[i]是next数组.如下图，若错位部分不是一个最小循环节（假设是循环串，必定有循环节），那么匹配部分可以更长，矛盾，因此i-f[i]是最小循环节。
又假设i-f[i]是一个最小循环节，根据下图红色箭头可知串是一个回文串。
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<utility>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define Inf (1<<30)
#define LL long long
#define MOD 1000000009
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
int f[1000100];
char s[1000010];
int main()
{int T,o=1;int n,m;///freopen("D:\\oo.txt","r",stdin);while(~scanf("%d",&n)&&n){scanf("%s",s);f[0]=f[1]=0;int L=strlen(s);for(int i=1;i<L;i++){int j=f[i];while(j&&s[i]!=s[j])j=f[j];f[i+1]=(s[j]==s[i]?j+1:0);}printf("Test case #%d\n",o++);for(int i=2;i<=L;i++){if(f[i]>0&&i%(i-f[i])==0)printf("%d %d\n",i,i/(i-f[i]));}puts("");}return 0;
}
这篇关于uvalive3026（kmp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
