2320: 最多重复子串 - #include <Seter> - using namespace Orz;
2320: 最多重复子串
http://www.zybbs.org/JudgeOnline/problem.php?id=2320
| RunID | User | Problem | Result | Memory | Time | Language | Code_Length | Submit_Time |
| 221998 | Seter | 2320 | Accepted | 2516 kb | 4632 ms | C/Edit | 1229 B | 2012-03-11 20:22:04 |
比较裸。。。rank1的神犇估计是O(nlgn)的神算法，像我这种苣蒻只能水水O(nlg^2n)的hash。。不过代码长度可以虐场。。
那啥。。。这个东西09年的论文里有。。。如果我说的太2B了大家可以去看那篇论文。。
首先，如果最大重复次数是1，那么答案就是最小的那个字符。。。预处理出来。
然后假设答案是ppp...p(p为一个串)，则p至少出现2次。
枚举p的长度L，则如果出现了答案，一定会有a[kL],a[kL+L]切在两个相邻的p的同一位置。
那么只要再枚举k，然后对于a[kL]和a[kL+L]求一下LCP和LCS（这个S是Suffix，懒得打中文了）就好了。。
对于长度为L的p，a[kL]和a[kL+L]可以提供的重复次数就是(LCP+LCS-1)/L+1，用这个去更新即可。
但是还没结束，可以提供的重复次数是唯一的，但是提供的答案不是唯一的。。比如babab,L=2的时候。。。
这下怎么办呢？我的方法是直接枚举可能的起始点。。。这样看似是O(n^2)的，但是可以证明L从小到大枚举时，update的次数是严格小于n的。。。
总复杂度的话，update总共是O(nlgn)的。枚举L的时候，再枚举k是O(n/L)，总共就是O(nlgn)次；每次要二分一下，总复杂度是O(nlg^2n)。
#include<stdio.h>
#define N 100100
#define BASE 13331
#define get(i,j) (h[j]-h[(i)-1]*P[(j)-(i)+1])
char*str,s[N*10],*p=s;
int hp[N],*h=hp+1,P[N]={1},ar,al,aa,n;
inline LCP(i,j,k,b,c)int*k,i,j,*b;_Bool c;{
int l=0,r;if(str[i]!=str[j])return *k=*b=0;
if(i>j)i^=j^=i^=j;
#define mid (l+r>>1)
if(c)for(r=i+1;l+1!=r;)if(get(i-mid,i-1)==get(j-mid,j-1))l=mid;else r=mid;
*k=l;for(l=0,r=n-j;l+1!=r;)if(get(i+1,i+mid)==get(j+1,j+mid))l=mid;else r=mid;
return(*b=l)+1+*k;
}inline void Updt(r,a,l){
int t,k,b;
if(r!=ar){ar=r;aa=a;al=l;return;}
if((t=LCP(a,aa,&k,&b,0))>=l||t>=al){if(l<al)ar=r,aa=a,al=l;return;}
if(str[a+t]<str[aa+t])ar=r,aa=a,al=l;
}main(){
int t,i=0,j,k,L,c,b;
while(++i!=N)P[i]=P[i-1]*BASE;
for(scanf("%d",&t),fread(p,1,N*10,stdin);t--;){
while(!islower(*p))p++;
str=p;ar=al=1;aa=0;
for(n=-1;islower(str[++n]);h[n]=h[n-1]*BASE+str[n])if(str[aa]>str[n])aa=n;
p=str+n;
for(L=0;++L<<1<=n;)for(i=0;++i*L<n;)if((k=LCP(i*L-L,i*L,&j,&b,1)/L+1)>=ar&&k!=1)for(c=-1;++c+(k-1)*L-j<=b+1;)Updt(k,i*L-L-j+c,k*L);
str[aa+al]=0;puts(str+aa);
}return 0;
}
By Seter
2012年4月08日 17:52
這題可以o(n)的.SPOJ上nlogn的都不知道被刷到哪裡去了.
2012年4月08日 19:46
啊。。。求标程。。。。没看到SPOJ上这题。。。
2012年4月09日 14:08
http://www.spoj.pl/problems/REPEATS/ 標程木有.標程應該是字符串分解
2012年4月09日 18:23
只会nlgn。。。囧 T T 弱暴了
2012年4月16日 09:06
#include<cstdio>
#include<cstring>
#define MAXN 51000
#define C(Now,i) c[Now][Str[i+d[Now]]]
int t,c[2*MAXN][3],d[2*MAXN],f[2*MAXN],Link[2*MAXN],Str[MAXN],Case,n,N,Ans,F[2*MAXN],bl[2*MAXN],Pos[2*MAXN],
Fac[2*MAXN],Beg[2*MAXN],End[2*MAXN],Pre[2*MAXN],Suc[2*MAXN],_x[4*MAXN],_y[4*MAXN],_f[2*MAXN],_T,T;
char Chr;
void read(int&x)
{ for(;(Chr=getchar())<'0';);
for(x=Chr-'0';(Chr=getchar())>='0';x=x*10+Chr-'0');
}
void readc(int&x)
{ for(;(Chr=getchar())<'0';);
x=Chr-'a';
}
void Cut(int&x,int Len,int i)
{ if(!Len)return;
d[++t]=d[x]+Len;
f[t]=f[C(x,i)]-d[C(x,i)]+d[t];
c[t][Str[f[t]]]=C(x,i);
x=C(x,i)=t;
}
void Build_Suffix_Tree()
{ int i,Now(1),Len(0),Far,j,k;
Link[1]=1;
for(i=0;i<n;i++,Now=Link[Far])
{ for(Len=0;C(Now,i)&&Str[f[C(Now,i)]-d[C(Now,i)]+d[Now]+Len]==Str[i+d[Now]+Len];)
if(d[Now]+(++Len)==d[C(Now,i)]){Now=C(Now,i);Len=0;}
Cut(Far=Now,Len,i);
f[C(Far,i)=++t]=n;
d[Pos[i]=t]=n-i;
for(k=Far,j=i+1;!Link[k];k=Link[k])
{ for(Link[k]=Link[Now];C(Link[k],j)&&d[C(Link[k],j)]+1<=d[k];Link[k]=C(Link[k],j));
Now=Link[k];
Cut(Link[k],d[k]-d[Link[k]]-1,j++);
}
Fac[i]=d[Far]?d[Far]:1;
}
}
void String_Factorization()
{ int i,j,k;
T=0;
for(i=j=0;i<N;i+=Fac[j=i])
for(k=(j-Fac[i]+1)>0?(j-Fac[i]+1):0;k<i;k++)if(Str[k]==Str[i])
{ Beg[++T]=k;
End[T]=i;
}
}
void IN(int a,int b){_x[_T]=_f[Pos[a]];_y[_T]=Pos[b];_f[Pos[a]]=_T++;}
int Find(int x){return F[x]==x?x:F[x]=Find(F[x]);}
void Tarjan(int*P,int l)
{ bl[F[l]=l]=1;
int i;
for(i=0;i<3;i++)
if(c[l][i])
{ Tarjan(P,c[l][i]);
F[c[l][i]]=l;
}
for(i=_f[l];i;i=_x[i])
if(bl[_y[i]])
P[i>>1]=d[Find(_y[i])];
}
int main()
{ int i,j;
freopen("REPEATS.in","rb",stdin);
freopen("REPEATS.out","wb",stdout);
for(read(Case);Case--;)
{ read(N);
for(i=0;i<N;i++)readc(Str[i]);
n=N+1;
Str[N]=2;
memset(c,0,(t+1)*sizeof c[0]);
memset(bl,0,(t+1)*sizeof(int));
memset(_f,0,(t+1)*sizeof(int));
memset(Link,0,(t+1)*sizeof(int));
t=1;
Build_Suffix_Tree();
String_Factorization();
_T=2;
for(i=1;i<=T;i++)
{ IN(Beg[i],End[i]);
IN(End[i],Beg[i]);
}
Tarjan(Pre,1);
for(i=0;2*i<N;i++)
{ j=Str[i];
Str[i]=Str[N-i-1];
Str[N-i-1]=j;
}
n=N+1;
Str[N]=2;
memset(c,0,(t+1)*sizeof c[0]);
memset(bl,0,(t+1)*sizeof(int));
memset(_f,0,(t+1)*sizeof(int));
memset(Link,0,(t+1)*sizeof(int));
t=1;
Build_Suffix_Tree();
_T=2;
for(i=1;i<=T;i++)
{ IN(N-Beg[i]-1,N-End[i]-1);
IN(N-End[i]-1,N-Beg[i]-1);
}
Tarjan(Suc,1);
Ans=0;
for(i=1;i<=T;i++)
if(Ans<(Pre[i]+Suc[i]-1)/(End[i]-Beg[i]))
Ans=(Pre[i]+Suc[i]-1)/(End[i]-Beg[i]);
printf("%d\n",Ans+1);
}
return 0;
}
2012年4月16日 09:07
我去寫了一下...還是有點慢..2.14s
2012年4月16日 18:27
太神了 T T 完全看不懂。。。
2024年1月16日 20:26
Nice info, thanks for share,