Period

KMP 啊 错位部分是一个循环节啊

 

#include<iostream>  
#include<string>  
#include<stdio.h>  
using namespace std;  
string s;  
int n;  
int next[1000010];  
  
  
void getnext()  
{  
    int min =1;  
    int x;  
    int k=-1,j=0;  
    next[0]=-1;  
    while(j<n)  
    {  
        if(k==-1||s[j]==s[k])  
        {  
            j++;  
            k++;  
            next[j]=k;  
            if(j%(j-k)==0&&j/(j-k)>1)  
            printf("%d %d\n",j,j/(j-k));  
        }  
        else  
            k=next[k];    
    }  
}  
int main()  
{  
    int cnt =1;  
    while(cin>>n,n)  
    {  
        cin>>s;  
        printf("Test case #%d\n",cnt++);  
        getnext();  
        puts("");  
    }  
    return 0;  
}