POJ 2406 字元串循環節

字尾數組處理1e6的字元串會逾時（常數比較大），換成hash或kmp

對fail數組的又一個了解（移位之後比對）

這題倒着想賊好想，若循環子串，則必然滿足 這個 fail 數組的性質，也可證明，滿足這個性質即為循環子串

#include<cstdio>
#include<cstring>
typedef long long LL;
typedef int lint;
const lint maxn = 1000000 + 5;
char s[maxn];
lint fail[maxn];
void get_fail( char * str ){
    lint len = strlen( str );
    fail[0] = -1;
    for( lint i = 1;i < len;i++ ){
        lint p = fail[i-1];
        while( p != -1 && s[p+1] != s[i] ) p =fail[p];
        if( s[p+1] == s[i] ) fail[i] = p+1;
        else fail[i] = -1;
    }
}
int main(){

    while(~scanf("%s",s)){
    if( !strcmp( s,"." ) ) break;
    get_fail( s );
    lint len = strlen(s);
    lint ans = len;
    lint p = fail[len-1];
    if( p == -1 ){
        printf("1\n");
        continue;
    }
    do{
        lint le =  2*( p+1 )-len;
        if( le % (len-p-1) == 0 ){
            ans = len-p-1;
            break;
        }
        p = fail[p];
    }while( p != -1 );
    printf("%d\n", len/ans );
    }
    return 0;
}