Description
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).
Input
Each test case is a line of input representing s, a string of printable characters. 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.
Output
For each s you should print the largest n such that s = a^n for some string a.
Sample Input
abcd
aaaa
ababab
.
Sample Output
1
4
3
Hint
This problem has huge input, use scanf instead of cin to avoid time limit exceed.
题解
(PS:)这题的正解是(KMP)算法，这里还给出超时的(Lcp)与侥幸过了的暴力
暴力
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int L=1001001;
int l,id; char s[L];
int Check()
{
for(int i=id;i<l;++i)
if(s[i]!=s[i-id]) return 0;
return 1;
}
int main()
{
int Ans;
for(scanf("%s",s);s[0]!='.';scanf("%s",s))
{
l=strlen(s);
Ans=1;
for(int i=l;i>=2;--i)
{
if(l%i) continue;
id=l/i;
if(Check()) {Ans=i;break;}
}
printf("%d
",Ans);
}
return 0;
}
(KMP)
(KMP)的巧妙之处在于它的(next)数组，该数组能反映字符串的对称性
这题还有一个坑点，要加上特判
if(l%(l-nt[l])==0) Ans=l/(l-nt[l]);
即可以分解为整数个子串
(My~Code)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int L=1001001;
int l,nt[L];
char s[L];
void Make_nt()
{
int i=0,j=-1;
nt[i]=-1;
while(i<l)
{
if(j==-1||s[i]==s[j])
++i,++j,nt[i]=j;
else j=nt[j];
}
}
int main()
{
int len,Ans;
for(scanf("%s",s);s[0]!='.';scanf("%s",s))
{
l=strlen(s);
Make_nt();
Ans=1;
if(l%(l-nt[l])==0) Ans=l/(l-nt[l]);
printf("%d
",Ans);
}
return 0;
}
超时的(Lcp)
(My~Code)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1001001;
int n,sa[N],rk[N],tmp[N],c[N],height[N],Qz[N];
char s[N];
void Make_Sa()
{
int i,j,len,na;
na=256;
memset(c,0,na*sizeof(int));
for(i=0;i<n;++i)
{
rk[i]=s[i]&0xff,
++c[rk[i]];
}
for(i=1;i<na;++i) c[i]+=c[i-1];
for(i=0;i<n;++i)
{
--c[rk[i]],
sa[c[rk[i]]]=i;
}
for(len=1;len<n;len<<=1)
{
for(i=0;i<n;++i)
{
j=sa[i]-len;
if(j<0) j+=n;
tmp[c[rk[j]]++]=j;
}
c[0]=0,j=0,
sa[tmp[0]]=0;
for(i=1;i<n;++i)
{
if(rk[tmp[i]]!=rk[tmp[i-1]]
||rk[tmp[i]+len]!=rk[tmp[i-1]+len])
c[++j]=i;
sa[tmp[i]]=j;
}
memcpy(rk,sa,n*sizeof(int)),
memcpy(sa,tmp,n*sizeof(int));
if(j>=n-1) break;
}
}
void Lcp()
{
int i=0,j,k=0;
height[0]=0;
for(j=rk[0];i<n-1;++i,++k)
for(;k>=0&&s[i]!=s[sa[j-1]+k];)
{
height[j]=k, --k;
j=rk[sa[j]+1];
}
}
void Solve()
{
Qz[rk[0]]=n-1;
for(int i=rk[0]-1;i;--i) Qz[i]=min(Qz[i+1],height[i+1]);
for(int i=rk[0]+1;i<n;++i) Qz[i]=min(Qz[i-1],height[i-1]);
int Ans=-1;
--n;
for(int i=1;i<=n;++i)
{
if(n%i) continue;
if(Qz[rk[i]]==n-i)
{
Ans=n/i;
break;
}
}
printf("%d
",Ans);
}
int main()
{
for(;;)
{
scanf("%s",s);
n=strlen(s);
if(n==1&&s[0]=='.') break;
s[n++]=1;
Make_Sa(),Lcp(),Solve();
}
return 0;
}
字符串(Hash)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
typedef unsigned long long ull;
const int E=10007;
const int LEN=1000002;
int len,Ans,l;
char c[LEN];
ull power[LEN],h[LEN];
int main()
{
power[0]=1;
for(int i=1;i<LEN;++i) power[i]=power[i-1]*E;
for(scanf("%s",c+1);c[1]!='.';scanf("%s",c+1))
{
len=strlen(c+1);
for(int i=1;i<=len;++i) h[i]=h[i-1]*E+c[i];
Ans=1;
for(int i=len;i>=2;--i)
{
if(len%i) continue;
l=len/i;
if(h[len-l]==(h[len]-h[l]*power[len-l]))
{Ans=i; break;}
}
printf("%d
",Ans);
}
return 0;
}