Power Strings

POJ

题意:给定若干个长度小于等于\(1e6\)的小写字母字符串,询问每个字符串最多由多少个相同的子串重复连接而成.

分析:字符串哈希记录字符串每一段的值.然后从小到大枚举\(n\)(设\(n\)为字符串的长度)的约数,判断每一段约数长度的哈希值是否相等即可.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=1000005;
char s[N];int p=1e9+7;
ull Base[N],sum[N];
int main(){
    Base[0]=1;for(int i=1;i<N;++i)Base[i]=Base[i-1]*p;
    while(1){
        scanf("%s",s+1);if(s[1]=='.')break;
        int n=strlen(s+1);sum[0]=0;
        for(int i=1;i<=n;++i)
            sum[i]=sum[i-1]*p+(ull)s[i]-'a'+1;//懒得写双哈希了
        for(int i=1;i<=n;++i){//枚举约数
            if(n%i)continue;//不是约数就直接跳过
            ull s=sum[i]-sum[0];//先算出第一段
            int bj=1;
            for(int j=i;j+i<=n;j+=i){
                if(sum[j+i]-sum[j]*Base[i]!=s){//如果这个不满足就跳出,节约时间
                    bj=0;break;
                }
            }
            if(bj){//如果当前约数满足,直接输出,保证最大
                printf("%d\n",n/i);
                break;
            }
        }
    }
    return 0;
}