模板库

procedure sort(l,r:longint);
var i,j,mid:longint;
begin
  i:=l;j:=r;mid:=a[(l+r) shr 1];
  repeat
    while a[i]<mid do inc(i);
    while mid<a[j] do dec(j);
    if i<=j then
    begin
      swap(a[i],a[j]);
      inc(i);dec(j);
    end;
  until i>j;
  if i<r then sort(i,r);
  if j>l then sort(l,j);
end;

program uoj35;
const maxn=100010;
type arr=array[0..maxn] of longint;
var cnt,x0,y0,sa,rank,height:arr;
    x,y,t:^arr;
    s:ansistring;
    n,m,p,k,i,j:longint;
begin
  readln(s);
  n:=length(s);
  m:=128;
  for i:=1 to n do x0[i]:=ord(s[i]);
  fillchar(cnt,sizeof(cnt),0);
  for i:=1 to n do inc(cnt[x0[i]]);
  for i:=1 to m do cnt[i]:=cnt[i]+cnt[i-1];
  for i:=n downto 1 do
    begin
      sa[cnt[x0[i]]]:=i;
      dec(cnt[x0[i]]);
    end;
  k:=1;
  x:=@x0;
  y:=@y0;
  while true do
    begin
      p:=0;
      for i:=n-k+1 to n do begin inc(p); y^[p]:=i; end;
      for i:=1 to n do
        if sa[i]>k then
          begin
            inc(p);
            y^[p]:=sa[i]-k;
          end;
      fillchar(cnt,sizeof(cnt),0);
      for i:=1 to n do
        inc(cnt[x^[y^[i]]]);
      for i:=1 to m do cnt[i]:=cnt[i]+cnt[i-1];
      for i:=n downto 1 do
        begin
          sa[cnt[x^[y^[i]]]]:=y^[i];
          dec(cnt[x^[y^[i]]]);
        end;
      t:=x; x:=y; y:=t;
      p:=0;
      for i:=1 to n do
        begin
          if (y^[sa[i]]<>y^[sa[i-1]])or(y^[sa[i]+k]<>y^[sa[i-1]+k]) then inc(p);
          x^[sa[i]]:=p;
        end;
      if p>=n then break;
      m:=p;
      k:=k shl 1;
    end;
  for i:=1 to n do
    write(sa[i],‘ ‘);
  writeln;
  for i:=1 to n do rank[sa[i]]:=i;
  p:=0;
  for i:=1 to n do
    begin
      if rank[i]=1 then continue;
      if p>0 then dec(p);
      j:=sa[rank[i]-1];
      while(i+p<=n)and(j+p<=n)and(s[i+p]=s[j+p]) do inc(p);
      height[rank[i]]:=p;
    end;
  for i:=2 to n do write(height[i],‘ ‘);
end.