| ||||||||||
| 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