[KMP]poj 1961：Period

大致题意：
    给出一个长度为n的字符串，分别求出前n位前缀，分别可以由多少个相同的子串连接而成。

 

大致思路：

    依旧是next数组的灵活运用，和poj2406差不多，在此不在赘述。

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=1000005;
char pat[nMax];
int lenp,next[nMax];

void get_next(){
    int i,j=-1;
    next[0]=-1;
    for(i=1;i<=lenp;i++){
        while(j>-1&&pat[j+1]!=pat[i])j=next[j];
        if(pat[j+1]==pat[i])j++;
        next[i]=j;
    }
}

int main(){
    int cas=0;
    while(scanf("%d",&lenp)!=EOF&&lenp){
        cas++;
        scanf("%s",pat);
        printf("Test case #%d\n",cas);
        get_next();
        for(int i=2;i<=lenp;i++){
            int l=(i-1)-next[i-1];
            if(i%l==0&&i!=l){
                cout<<i<<" "<<i/l<<endl;;
            }
        }
        printf("\n");
    }
    return 0;
}