首页 > 代码库 > 【SPOJ220】Relevant Phrases of Annihilation (SA)

【SPOJ220】Relevant Phrases of Annihilation (SA)

成功完成3连T!   嗯没错,三道TLE简直爽到不行,于是滚去看是不是模版出问题了..拿了3份其他P党的模版扔上去,嗯继续TLE...蒟蒻表示无能为力了...

思路像论文里面说的,依旧二分长度然后分组...然后记录下每个字符的最大和最小值去判断是否满足全部成立...完事...写起来其实蛮简单的...

const maxn=100419;var h,sum,rank,x,y,sa,c,lx,rx,col:array[0..maxn] of longint; n,k,maxlen,t,q:longint; s:ansistring;function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end;function min(x,y:longint):longint; begin if x<y then exit(x) else exit(y); end;procedure swap(var x,y:longint); var tmp:longint; begin tmp:=x;x:=y;y:=tmp; end;procedure make;var p,i,j,tot:longint;begin while p<n do  begin   fillchar(c,sizeof(c),0);   for i:= 1 to n-p do y[i]:=rank[i+p];   for i:= n-p+1 to n do y[i]:=0;   for i:= 1 to n do inc(c[y[i]]);   for i:= 1 to n do inc(c[i],c[i-1]);   for i:= 1 to n do    begin     sa[c[y[i]]]:=i;     dec(c[y[i]]);    end;   fillchar(c,sizeof(c),0);   for i:= 1 to n do x[i]:=rank[i];   for i:= 1 to n do inc(c[x[i]]);   for i:= 1 to n do inc(c[i],c[i-1]);   for i:= n downto 1 do    begin     y[sa[i]]:=c[x[sa[i]]];     dec(c[x[sa[i]]]);    end;   for i:= 1 to n do sa[y[i]]:=i;   tot:=1;   rank[sa[1]]:=1;   for i:= 2 to n do    begin     if (x[sa[i]]<>x[sa[i-1]]) or (x[sa[i]+p]<>x[sa[i-1]+p]) then inc(tot);     rank[sa[i]]:=tot;    end;   if tot=n then break;   p:=p<<1;  end; for i:= 1 to n do sa[rank[i]]:=i; h[1]:=0; p:=0; for i:= 1 to n do  begin   p:=max(p-1,0);   if rank[i]=1 then continue;   j:=sa[rank[i]-1];   while (j+p<=n) and (i+p<=n) and (s[i+p]=s[j+p]) do inc(p);   h[rank[i]]:=p;  end;end;procedure init;var i,j,tot,p,m:longint; s1:ansistring;begin readln(k); readln(s); for i:= 1 to length(s) do col[i]:=1; maxlen:=length(s); for i:= 2 to k do  begin   readln(s1);   maxlen:=max(length(s1),maxlen);   s:=s+#;   for j:= length(s)+1 to length(s)+length(s1) do col[j]:=i;   s:=s+s1;  end; n:=length(s); fillchar(c,sizeof(c),0); for i:= 1 to n do x[i]:=ord(s[i]); for i:= 1 to n do inc(c[x[i]]); for i:= 1 to 128 do inc(c[i],c[i-1]); for i:= 1 to n do  begin   sa[c[x[i]]]:=i;   dec(c[x[i]]);  end; tot:=1; rank[sa[1]]:=1; for i:= 2 to n do  begin   if x[sa[i]]<>x[sa[i-1]] then inc(tot);   rank[sa[i]]:=tot;  end; make;end;function check(len:longint):boolean;var i,j,t,cnt:longint;begin for i:= 1 to n do  begin   if h[i]<len then    begin     fillchar(lx,sizeof(lx),$7f);     fillchar(rx,sizeof(rx),0);     lx[col[sa[i]]]:=sa[i];     rx[col[sa[i]]]:=sa[i];    end   else    begin     t:=col[sa[i]];     lx[t]:=min(lx[t],sa[i]);     rx[t]:=max(rx[t],sa[i]);     cnt:=0;     for j:= 1 to k do if rx[j]-lx[j]+1>=len then inc(cnt);     if cnt=k then exit(true);    end;  end; exit(false);end;procedure solve;var l,r,mid,ans:longint;begin l:=1; r:=maxlen; ans:=0; while l<=r do  begin   mid:=(l+r)>>1;   if check(mid) then    begin     ans:=mid;     l:=mid+1;    end   else r:=mid-1;  end; writeln(ans);end;Begin readln(t); for q:= 1 to t do  begin   init;   solve;  end;End.

 

【SPOJ220】Relevant Phrases of Annihilation (SA)