Power Strings
题意简述:
求一个字符串由多少个重复的子串连接而成。
例如 ababab
由三个 ab
连接而成,abcd
由 abcd
由一个 abcd
连接而成。
输入格式
本题多组数据。
每一组数据仅有一行,这一行仅有一个字符串 s s s。
输入的结束标志为一个 .
。
输出格式
对于每一组数据,输出这组字符串由多少个重复的子串连接而成。
说明/提示
1 ≤ ∣ s ∣ ≤ 1 0 6 1\le |s|\le 10^6 1≤∣s∣≤106。
题目描述
输入格式
输出格式
样例 #1
样例输入 #1
abcd
aaaa
ababab
.
样例输出 #1
1
4
3
大致思路
基本套模板即可
只需求出每次输入的主字符串的哈希函数值,枚举可能的子串长度,再判断子串哈希值是否合法即可
理论实现:
首先,子串长度要能被主串长度整除。
其次,假设我们当前枚举的子串长度为K,则我们需要判断 s t r [ 1 ] str[1] str[1]到 s t r [ K ] str[K] str[K], s t r [ K + 1 ] str[K+1] str[K+1]到 s t r [ 2 K ] str[2K] str[2K]… 以此类推。
再根据 H ( C ′ ) = H ( C , k + n ) − H ( C , k ) ∗ b n H(C')=H(C,k+n)-H(C,k)*b^n H(C′)=H(C,k+n)−H(C,k)∗bn即可判断。
代码实现
bool check(ull a,ull len){//子串判断for(int i=1;i<=n;i+=len){if(a!=sum[i+len-1]-sum[i-1]*poww[len])return 0;}return 1;
}
poww[0]=1;for(int i=1;i<=N-99;i++){poww[i]=poww[i-1]*b;}scanf("%s",s+1);
while(s[1]!='.'){sum[0]=0;n=strlen(s+1);for(int i=1;i<=n;i++){sum[i]=sum[i-1]*b+(ull)(s[i]);}for(int i=1;i<=n;i++){if(n%i!=0)continue;ull k=sum[i];if(check(k,i)){//当前长度是否合法cout<<n/i<<endl;break;}}scanf("%s",s+1);}