Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:3261 problemIn Reply To:3261 problem Posted by:4891334 at 2007-10-29 10:00:35 > please help to solve this problem!!! var sa,rank,height,key1,key2,a:array [0..200000] of longint; n,m:longint; procedure qsort(x,y:longint); var p,q,mid1,mid2,t:longint; begin p:=x; q:=y; mid1:=key1[(x+y) div 2]; mid2:=key2[(x+y) div 2]; repeat while (key1[x]<mid1) or ((key1[x]=mid1) and (key2[x]<mid2)) do inc(x); while (key1[y]>mid1) or ((key1[y]=mid1) and (key2[y]>mid2)) do dec(y); if x<=y then begin t:=key1[x]; key1[x]:=key1[y]; key1[y]:=t; t:=key2[x]; key2[x]:=key2[y]; key2[y]:=t; t:=sa[x]; sa[x]:=sa[y]; sa[y]:=t; inc(x); dec(y); end; until x>y; if x<q then qsort(x,q); if p<y then qsort(p,y); end; procedure init; var i,tot:longint; begin readln(n,m); fillchar(a,sizeof(a),0); fillchar(key2,sizeof(key2),0); for i:=1 to n do begin readln(a[i]); key1[i]:=a[i]; sa[i]:=i; end; qsort(1,n); rank[sa[1]]:=1; tot:=1; for i:=2 to n do begin if (key1[i]<>key1[i-1]) or (key2[i]<>key2[i-1]) then inc(tot); rank[sa[i]]:=tot; end; end; procedure suffix_array; var i,tot,p:longint; begin p:=1; while p<n do begin for i:=1 to n do key1[i]:=rank[i]; for i:=1 to n do key2[i]:=rank[i+p]; for i:=1 to n do sa[i]:=i; qsort(1,n); rank[sa[1]]:=1; tot:=1; for i:=2 to n do begin if (key1[i]<>key1[i-1]) or (key2[i]<>key2[i-1]) then inc(tot); rank[sa[i]]:=tot; end; if tot=n then break; p:=p*2; end; for i:=1 to n do rank[sa[i]]:=i; end; procedure make_height; var i,j,h:longint; begin h:=0; for i:=1 to n do begin if rank[i]=1 then begin height[1]:=0; continue; end; j:=sa[rank[i]-1]; while a[i+h]=a[j+h] do inc(h); height[rank[i]]:=h; if h>0 then dec(h); end; end; function ok(x:longint):boolean; var i,j,k:longint; begin k:=1; for i:=1 to n do begin if height[i]>=x then inc(k) else k:=1; if k>=m then exit(true); end; exit(false); end; procedure main; var l,r,mid,ans:longint; begin ans:=0; l:=0; r:=n; while l<=r do begin mid:=(l+r) div 2; if ok(mid) then begin ans:=mid; l:=mid+1 end else r:=mid-1; end; writeln(ans); end; begin init; suffix_array; make_height; main; end. Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator