LA3026&&POJ1961Period（KMP算法）

题意：给定一个长度为n字符串s，求它每个前缀的最短循环节。也就是对于每个i（2<=i<=n)，求一个最大整数k>1（如果存在），使得s的前i个字符组成的前缀是某个字符串重复得k次得到的。输出所有的的k和i。

析：首先这是一个KMP的一个题（据大神们说这是一个水题。。。），首先要对KMP有了解，如果没有了解的先看一下，提供一个地址学习KMP算法，

http://www.cnblogs.com/dwtfukgv/articles/5532277.html

对KMP有所了解后，其实这就是一个对失配函数（f[x]）的运用，首先来说，我们对根据它的定义，“错位部分”长度为i-f[i]。如果这i个字符组成一个周期串的话，那么“错位”部分恰好必须是一个循环节，因此k*（i-f[i]） = i，（注意中k>1，所以i-f[i]!=i,也就是必须有f[i] > 0）。反过来也成立。如果对KMP了解了，那么应该是挺简单的理解的。

代码如下：

#include 
#include 

using namespace std;
const int maxn = 1000000 + 10;
char p[maxn];
int f[maxn];

int main(){
    int n, kase = 0;
    while(scanf("%d", &n), n){
        scanf("%s", p);
        f[0] = f[1] = 0;
        for(int i = 1; i  0 && i % (i - f[i]) == 0)  printf("%d %d\n", i, i / (i - f[i]));
        printf("\n");
    }
    return 0;
}