2320: 最多重复子串 - #include <Seter> - using namespace Orz;

2320: 最多重复子串

Seter posted @ 2012年3月15日 16:39 in BZOJ with tags String Hash , 2694 阅读

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
Avatar_small
kmxyvb 说:
2012年4月08日 17:52

這題可以o(n)的.SPOJ上nlogn的都不知道被刷到哪裡去了.

Avatar_small
Seter 说:
2012年4月08日 19:46

啊。。。求标程。。。。没看到SPOJ上这题。。。

Avatar_small
kmxyvb 说:
2012年4月09日 14:08

http://www.spoj.pl/problems/REPEATS/ 標程木有.標程應該是字符串分解

Avatar_small
Seter 说:
2012年4月09日 18:23

只会nlgn。。。囧 T T 弱暴了

Avatar_small
kmxyvb 说:
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;
}

Avatar_small
kmxyvb 说:
2012年4月16日 09:07

我去寫了一下...還是有點慢..2.14s

Avatar_small
Seter 说:
2012年4月16日 18:27

太神了 T T 完全看不懂。。。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee