首页 > 代码库 > 【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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。