Power Strings

给定字符串最多可以写成几个相同的接在一起？

Solution

有点暴力
先搞个hash， 然后暴力枚举len的因子， 那hash判断是否符合条件

Code

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<climits>
#define LL long long
#define REP(i, x, y) for(LL i = (x);i <= (y);i++)
using namespace std;
LL RD(){
    LL out = 0,flag = 1;char c = getchar();
    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
    return flag * out;
    }
const LL maxn = 1000010, mod = 1e9 + 9, base = 233;
char s[maxn];
LL p[maxn], hash[maxn], len;
void init(){
	p[0] = 1;
	REP(i, 1, maxn - 5)p[i] = p[i - 1] * base % mod;
	}
LL get_hash(LL l, LL r){
	return ((hash[r] - hash[l - 1] * p[r - l + 1] % mod) % mod + mod) % mod;
	}
bool judge(LL x){
	LL l = 1, r = x;
	while(r <= len){
		if(get_hash(l, r) != get_hash(1, x))return 0;
		l += x, r += x;
		}
	return 1;
	}
void work(){
	len = strlen(s + 1);
	hash[0] = 0;
	REP(i, 1, len)hash[i] = (hash[i - 1] * base % mod + s[i] - 'a') % mod;
	REP(i, 1, len){
		if(len % i != 0)continue;
		if(judge(i)){
			printf("%d
", len / i);
			break;
			}
		}
	}
int main(){
	init();
	while(scanf("%s", s + 1)){
		if(s[1] == '.')return 0;
		work();
		}
	return 0;
	}