poj 2406 求连续重复子串出现的次数 后缀数组 (一)

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]

用倍增发超时 用dc3才行

[cpp]
#include
#include
#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) 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] else return r[a] void sort(int *r,int *a,int *b,int n,int m)
{
int i;
for(i=0;i for(i=0;i for(i=0;i for(i=1;i 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 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 rn[F(wb[i])]=c0(r,wb[i-1],wb[i]) p-1:p++;
if(p else for(i=0;i for(i=0;i if(n%3==1) wb[ta++]=n-1;
sort(r,wb,wa,ta,m);
for(i=0;i for(i=0,j=0,p=0;i sa[p]=c12(wb[j]%3,r,wa[i],wb[j]) wa[i++]:wb[j++];
for(;i for(;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 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< {
a=best[i-1][j];
b=best[i-1][j+(1<<(i-1))];
if(RMQ[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< a=best[t][a];b=best[t][b];
return RMQ[a] }
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--)
{