Power Strings
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 26591 Accepted: 11130
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.
Source
Waterloo local 2002.07.01
[Submit] [Go Back] [Status] [Disc
http://poj.org/problem?id=2406
問題描述：給定一個字符串L，已知這個字符串是由某個字符串S重復R次而得到的， 求R的最大值。
方法一：後綴數組。
從長度為1開始枚舉到長度為n，如果n%i==0，那麼判斷LCS (suff(i+0),suff(0))是否等於n-i。
根據h可以求得LCS，其中lcs(i,j)=min{h[rank[i]+1],...,h[rank[j]]}，其中假設rank[i]<rank[j]。
用倍增發超時 用dc3才行
[cpp]
#include <stdio.h>
#include<string.h>
#define maxn 1000001
char c;
int r[maxn*3],sa[maxn*3];
int ans[maxn];
char str[maxn*3];
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
int c0(int *r,int a,int b)
{return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];}
int c12(int k,int *r,int a,int b)
{if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
else return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];}
void sort(int *r,int *a,int *b,int n,int m)
{
int i;
for(i=0;i<n;i++) wv[i]=r[a[i]];
for(i=0;i<m;i++) ws[i]=0;
for(i=0;i<n;i++) ws[wv[i]]++;
for(i=1;i<m;i++) ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--) b[--ws[wv[i]]]=a[i];
return;
}
void dc3(int *r,int *sa,int n,int m) // r為待匹配數組 n為總長度 m為字符范圍
{
int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
r[n]=r[n+1]=0;
for(i=0;i<n;i++) if(i%3!=0) wa[tbc++]=i;
sort(r+2,wa,wb,tbc,m);
sort(r+1,wb,wa,tbc,m);
sort(r,wa,wb,tbc,m);
for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)
rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
if(p<tbc) dc3(rn,san,tbc,p);
else for(i=0;i<tbc;i++) san[rn[i]]=i;
for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3;
if(n%3==1) wb[ta++]=n-1;
sort(r,wb,wa,ta,m);
for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i;
for(i=0,j=0,p=0;i<ta && j<tbc;p++)
sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
for(;i<ta;p++) sa[p]=wa[i++];
for(;j<tbc;p++) sa[p]=wb[j++];
return;
}
int rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n) // 求height數組。
{
int i,j,k=0;
for(i=1;i<=n;i++) rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k)
for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
return;
}
int RMQ[maxn];
int mm[maxn];
///int best[20][maxn];//best[i][j] 表示從j開始的長度為2的i次方的一段元素的最小值
/*void initRMQ(int n)///O(Nlogn) 預處理
{
int i,j,a,b;
for(mm[0]=-1,i=1;i<=n;i++)
mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
for(i=1;i<=n;i++) best[0][i]=i;
for(i=1;i<=mm[n];i++)
for(j=1;j<=n+1-(1<<i);j++)
{
a=best[i-1][j];
b=best[i-1][j+(1<<(i-1))];
if(RMQ[a]<RMQ[b]) best[i][j]=a;
else best[i][j]=b;
}
return;
}
int askRMQ(int a,int b)///詢問a,b後綴的最長公共前綴 O(1)查詢
{
int t;
t=mm[b-a+1];b-=(1<<t)-1;
a=best[t][a];b=best[t][b];
return RMQ[a]<RMQ[b]?a:b;
}
int lcp(int a,int b)
{
int t;
a=rank[a];b=rank[b];
if(a>b) {t=a;a=b;b=t;}
return(height[askRMQ(a+1,b)]);
}
*/
int f[maxn];//f[i]表示lcp(0,i);
void get_f(int n)
{
int i,j,mmin;
j=rank[0];
mmin=999999999;
/*以下2個循環內的代碼順序不同的原因是 i和j的最長公共前綴lcp(rank[i],rank[j])的值應為
rmq(height,rank[i]+1,rank[j]) 注意有個+1
*/
for(i=j;i>=1;i--)
{
f[i]=mmin;
mmin=mmin<height[i]?mmin:height[i];//應該包括height[j]
}
mmin=999999999;
for(i=j+1;i<=n;i++)
{
mmin=mmin<height[i]?mmin:height[i]; //不應該包括height[j]
f[i]=mmin;
}
}
int main()
{
int i,n;
while(scanf("%s",str)!=EOF)
{
n=strlen(str);
if(n==1&&str[0]=='.') break;
for(i=0;i<n;i++) r[i]=str[i]-'a'+1;
r[n]=0;
dc3(r,sa,n+1,123);//千萬注意+1
calheight(r,sa,n);
// initRMQ(n);
/*
for(i=0; i<n+1; i++) // rank[i] : suffix(i)排第幾
printf("rank[%d] = %d\n",i,rank[i]);
printf("\n");
for(i=0; i<n+1; i++) // sa[i] : 排在第i個的是誰
printf("sa[%d] = %d\n",i,sa[i]);
*/
int len;
int mmax=0;
get_f(n);
for(len=1;len<=n;len++)
{
if(n%len==0)
{
if(f[rank[len]]==(n-len))
///注意是rank[len],因為這裡在求0和0+len的lcp ，即要求rank[0]到rank[len]之間的最小height值
{
mmax=n/len;
break;
}
}
}
if(mmax!=0)
printf("%d\n",mmax);
else printf("1\n");
}
return 0;
}
