学步园

非常恶心的一道题目，看了罗的论文，其中并没有说最小的字典序怎么处理，我整整写了3个RMQ，哎哟~~

总之就是先枚举单个循环节的长度，然后再枚举，找公共前缀（后缀），关于字典序还要写另外一个RMQ。。

100行的代码对于我这种喜欢缩行的人已经很恐怖了。。

program ex3;const ln2=1/ln(2);<br /> type arr=array[0..100001] of longint;<br /> var<br /> x,y,r,sa,c:arr;<br /> q,p,v:array[0..18] of arr;<br /> i,j,k,l,n,t,l1,l2,o1,o2,a1,a2,a3,max,ans1,ans2,ans3,task:longint;<br /> a:ansistring;<br /> function min(a,b:longint):longint;<br /> begin if a>b then min:=b else min:=a end;<br /> procedure sort(var a:arr;b:arr);<br /> begin<br /> fillchar(c,sizeof(c),0);<br /> for i:=1 to n do inc(c[a[i]+1]);<br /> for i:=1 to max do inc(c[i],c[i-1]);<br /> for i:=1 to n do begin<br /> inc(c[a[b[i]]]);sa[c[a[b[i]]]]:=b[i];<br /> end;<br /> end;<br /> begin<br /> readln(a);<br /> while a<>'#' do begin<br /> n:=length(a);inc(task);<br /> for i:=1 to n do begin<br /> sa[i]:=i;v[0,i]:=i;<br /> r[i]:=ord(a[i])-ord('a')+1;<br /> end;<br /> max:=28;l:=1;<br /> while max<>n do begin<br /> for i:=1 to n do<br /> if i+l<=n then y[i]:=r[i+l] else y[i]:=0;<br /> x:=r;sort(y,sa);sort(x,sa);<br /> max:=0;l:=l*2;<br /> for i:=1 to n do begin<br /> inc(max,ord((x[sa[i]]<>x[sa[i-1]])<br /> or(y[sa[i]]<>y[sa[i-1]])));<br /> r[sa[i]]:=max;<br /> end;<br /> end;<br /> l:=0;<br /> for i:=1 to n do begin<br /> dec(l,ord(l<>0));<br /> j:=i;k:=sa[r[i]-1];<br /> if r[i]=1 then continue;<br /> while (j+l<=n)and(k+l<=n)and(a[j+l]=a[k+l]) do inc(l);<br /> p[0,r[i]-1]:=l;<br /> end;<br /> l:=0;<br /> for i:=n downto 1 do begin<br /> dec(l,ord(l<>0));<br /> j:=i;k:=sa[r[i]+1];<br /> if r[i]=n then continue;<br /> while (j-l>0)and(k-l>0)and(a[j-l]=a[k-l]) do inc(l);<br /> q[0,r[i]]:=l;<br /> end;<br /> for i:=1 to trunc(ln(n)*ln2-1e-9)+1 do<br /> for j:=1 to n do begin<br /> k:=j+1<<(i-1);<br /> if k>n then k:=n;<br /> q[i,j]:=q[i-1,j];<br /> p[i,j]:=p[i-1,j];<br /> v[i,j]:=v[i-1,j];<br /> if q[i-1,k]<q[i,j] then q[i,j]:=q[i-1,k];<br /> if p[i-1,k]<p[i,j] then p[i,j]:=p[i-1,k];<br /> if r[v[i-1,k]]<r[v[i,j]] then v[i,j]:=v[i-1,k];<br /> end;<br /> ans2:=sa[1];<br /> ans1:=1;ans3:=1;<br /> for l:=1 to n>>1 do if n div l>=ans1 then<br /> for i:=1 to n div l-1 do begin<br /> o1:=r[i*l];o2:=r[i*l+l];<br /> if o1>o2 then begin<br /> j:=o1;o1:=o2;o2:=j;<br /> end;<br /> t:=trunc(ln(o2-o1)*ln2);<br /> l1:=min(p[t,o1],p[t,o2-(1<<t)]);<br /> l2:=min(q[t,o1],q[t,o2-(1<<t)]);<br /> k:=l1+l2-1;<br /> if (k div l+1>=ans1)and(k>=l) then begin<br /> a1:=k div l+1;a3:=l;<br /> o1:=i*l-l2+1;o2:=o1+k-(a1-1)*l;<br /> if o1=o2 then t:=0 else t:=trunc(ln(o2-o1)*ln2);<br /> a2:=v[t,o1];<br /> if r[v[t,o2-(1<<t)+1]]<r[a2]<br /> then a2:=v[t,o2-(1<<t)+1];<br /> if (a1>ans1)or(a1=ans1)and(r[a2]<r[ans2]) then begin<br /> ans1:=a1;ans2:=a2;ans3:=a3;<br /> end;<br /> end;<br /> end;<br /> writeln('Case ',task,': ',copy(a,ans2,ans3*ans1));<br /> readln(a);<br /> end;<br /> end.