# [HDU1358/UVA1328/SPOJ PERIDO/POJ1961/ZOJ2177]Period（KMP）

### Description

For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as A K , that is A concatenated K times, for some string A. Of course, we also want to know the period K.

KMP

## 解决思路

## 代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=1001000;
const int inf=2147483647;

int n;
char str[maxN];
int F[maxN];

int main()
{
int cas=0;
ios::sync_with_stdio(false);
while (cin>>n)
{
if (n==0) break;
cin>>(str+1);
F[1]=0;F[0]=-1;
for (int i=2;i<=n;i++)//得到Next数组
{
int j=F[i-1];
while ((j!=0)&&(str[j+1]!=str[i])) j=F[j];
if (str[j+1]==str[i]) F[i]=j+1;
else F[i]=0;
}
printf("Test case #%d\n",++cas);
for (int i=2;i<=n;i++)
if ((F[i]!=0)&&(i%(i-F[i])==0)) printf("%d %d\n",i,i/(i-F[i]));
printf("\n");
}
return 0;
}


HNCJ OIer 一枚