POJ 1961 循环子串

题意：输出每一个前缀的循环节，没有则不用输出。

思路：画出循环子串，观察期fail数组的特点。在思考加上什么条件使得fail数组称为判断循环串的充要条件。

#include 
#include 
using namespace std;
const int maxn = 1000005;
int f[maxn];
void get_fail( char* P,int *f ){
    int m = strlen(P);
    f[0] = -1;
    for( int i = 1;i < m;i++ ){
        int j = f[i-1];
        while( j != -1 && P[j+1]!=P[i] )j = f[j];
        if( P[j+1]==P[i] ) f[i] = j+1;
        else f[i] = -1;
    }
}
char str[maxn];
int main(){
    int n,ca = 0;
    while(1==scanf("%d",&n) && n ){
        printf("Test case #%dn",++ca);
        scanf("%s",str);
        get_fail( str,f );
        for( int i = 0;i < n;i++ ){
            if( f[i]*2+1-i >= 0 && (f[i]*2+1-i)%( i-f[i] ) == 0 ){
                int j = i-f[i];
                int k = (i+1)/j;
                printf("%d %dn",i+1,k);
            }
        }
        puts("");
    }
    return 0;
}