hdu 1358 KMP

題目大意：給出一個長度為 n 的字符串，求該字符串的循環前綴的長度，和循環次數；

示例：abababab
前4個字符，循環字串為ab,有2個循環周期 ab|ab
前6個字符，循環字串為ab,有3個循環周期 ab|ab|ab
前8個字符，循環字串為ab,有4個循環周期 ab|ab|ab|ab
輸出：
4 2
6 3
8 4

[cpp] #include<stdio.h>  
#define SIZE 1000006  
int next[SIZE]; 
char str[SIZE]; 
 
void getnext(int n) 
{ 
    int i=0,j=-1; 
    next[0]=-1; 
    while(i<n){ 
        if(j==-1 || str[i]==str[j]){ 
            i++; 
            j++; 
            next[i] = j; 
        } 
        else{ 
            j = next[j]; 
        } 
    } 
} 
int main() 
{ 
    int nT=1,n,i,mixed,circulate; 
    while(scanf("%d",&n),n){ 
        getchar(); 
        gets(str); 
        getnext(n); 
        printf("Test case #%d\n",nT++); 
        for(i=1;i<=n;i++){ 
            mixed = 2*next[i]-i;       //重疊部分  
            circulate = next[i]-mixed; //循環節長度  
            if(mixed>=0 && i%circulate==0){ 
                printf("%d %d\n",i,i/circulate); 
            } 
        } 
        printf("\n"); 
    } 
    return 0; 
}