后缀数组处理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;
}