Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

pascal 题解 (慢!jiong!188ms)

Posted by zhouzixuan at 2013-02-15 22:54:02 on Problem 3261
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator