时间限制: 1 Sec 内存限制: 128 MB 提交: 38 解决: 18 [提交] [状态] [讨论版] [命题人:外部导入]
题目描述
Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).
输入
Each test case is a line of input representing s, a string of printable characters.
输出
For each s you should print the largest n such that s = a^n for some stringa. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.
样例输入
abcd aaaa ababab .样例输出
1 4 3让你求，嗯，这个串是由最多多少个相同的小字符串构成的，
例如aaaa，可以使1个aaaa组成，也可以是两个aa，也可以是四个a
那么输出4，即最多几个
那么从最小的长度i = 1开始枚举，只有strlen(a)%i==0，才能恰好组成，否则跳过即可
对于%==0的情况暴力切割出所有的子串（事先hash），判断能否成立，
一旦出现成立，那么就是答案，
还有明显枚举到strlen(a)/2，即可，因为再往后枚举，都不成立的
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; const int maxn = 1e6+7; const pll k{1e9+9,1e9+7},p{1e9+7,1e9+9},one{1ll,1ll},zero{0ll,0ll}; pll operator - (pll a,pll b){return make_pair((a.first - b.first + p.first)%p.first,(a.second - b.second + p.second)%p.second);} pll operator * (pll a,pll b){return make_pair((a.first * b.first)%p.first,(a.second * b.second)%p.second);} pll operator + (pll a,pll b){return make_pair((a.first + b.first)%p.first,(a.second + b.second)%p.second);} pll operator + (pll a,int b){return make_pair((a.first + b)%p.first,(a.second + b)%p.second);} pll Hash(char a[],int len){ pll ans = zero; for(int i=0;i<len;i++) ans = ans*k + a[i]; return ans; } pll Pow(pll a,int n){ pll ans = one; while(n){ if(n&1)ans = ans*a; a = a*a; n>>=1; } return ans; } char a[maxn]; pll Len[maxn]; int main(){ while(cin>>a+1){ if(a[1]=='.')break; Len[0] = zero; for(int i=1;a[i];i++){ Len[i] = Len[i-1]*k + a[i]; } int ans = 1,la = (strlen(a+1)+1)/2,ln = strlen(a+1); for(int i=1;i<=la;i++){ if(ln%i)continue;///一个优化 int flag = 0; for(int j=i;!flag && j<=ln;j+=i) if(Len[j]-Len[j-i]*Pow(k,i)!=Len[i]) flag = 1; if(!flag){ ans = ln/i; break;///找到即跳出 } } cout<<ans<<endl; } return 0; }
