首页 > 代码库 > 【POJ3693】Maximum repetition substring (SA)
【POJ3693】Maximum repetition substring (SA)
这是一道神奇的题目..论文里面说得不清楚，其实是这样...如果一个长度为l的串重复多次，那么至少s[1],s[l+1],s[2*l+1],..之中有相邻2个相等...设这时为j=i*l+1,k=j+l,我们这时候借助SA和RMQ O(1)求出：m=lcp(j,k),这时候，重复次数至少ans=m div l+1 。 当然，我们枚举到不一定能够是最优啊，因为你枚举的不一定是字符串的首尾..那这时候怎么办？就是论文里面说的，向前和向后匹配。我们设t=l-m mod l..可以理解为，这时候 m mod l为多出来的字符，t就看成是前面少的字符个数..当然如果m mod l=0就不用管这个了...那也就是说，我们再判断是否lcp(j-t,k-t)>=l 如果成立，那么 ans++ ...因为可以多出一段..
上面就解决了求最长的问题，下面将关于字典序的这个...其实SA就是字典序了，只要枚举是否 lcp(sa[i],sa[i]+l)>=(ans-1)*l，若成立，显然当前sa[i]起始长度为l的字符串就是答案...
嗯..写完顿时觉得涨姿势了..
const maxn=100419;var rec,c,h,rank,sa,x,y:array[0..maxn] of longint; f:array[0..maxn,0..20] of longint; n,cas: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,tot:longint;begin p:=1; 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; p:=p<<1; end; for i:= 1 to n do sa[rank[i]]:=i;end;procedure makeh;var i,j,p:longint;begin 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 (i+p<=n) and (j+p<=n) and (s[i+p]=s[j+p]) do inc(p); h[rank[i]]:=p; end;end;procedure rmq;var i,j:longint;begin for i:= 1 to n do f[i,0]:=h[i]; for i:= 1 to trunc(ln(n)/ln(2)) do for j:= 1 to n-1<<i+1 do f[j,i]:=min(f[j,i-1],f[j+1<<(i-1),i-1]);end;procedure init;var i,tot:longint;begin n:=length(s); for i:= 1 to n do x[i]:=ord(s[i]); fillchar(c,sizeof(c),0); 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; rank[sa[1]]:=1; tot:=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; makeh; rmq;end;function lcp(x,y:longint):longint;var t:longint;begin x:=rank[x]; y:=rank[y]; if x>y then swap(x,y); if x<y then inc(x); t:=trunc(ln(y-x+1)/ln(2)); exit(min(f[x,t],f[y-1<<t+1,t]));end;procedure solve;var m,l,i,j,tmp,t,ans,cnt:longint; pd:boolean;begin init; fillchar(rec,sizeof(rec),0); ans:=0; for l:= 1 to n-1 do begin i:=1; while i+l<=n do begin m:=lcp(i,i+l); tmp:=m div l+1; t:=l-m mod l; t:=i-t; if (t>0) and (m mod l<>0) and (lcp(t,t+l)>=m) then inc(tmp); if tmp>ans then begin cnt:=1; rec[1]:=l; ans:=tmp; end; if cnt=ans then begin inc(cnt); rec[cnt]:=l; end; i:=i+l; end; end; pd:=false; for i:= 1 to n do if not pd then for j:= 1 to cnt do begin l:=rec[j]; if lcp(sa[i],sa[i]+l)>=(ans-1)*l then begin t:=sa[i]; l:=l*ans; pd:=true; break; end; end else break; inc(cas); write(‘Case ‘,cas,‘: ‘); for i:= t to t+l-1 do write(s[i]); writeln;end;Begin cas:=0; readln(s); while s[1]<>‘#‘ do begin solve; readln(s); end;End.
【POJ3693】Maximum repetition substring (SA)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。