后缀数组模板

procedure getrank;
 var
   i,j:longint;
   p,m:int64;
  begin
    m:=100;

    for i:=1 to len do
      rank[i]:=a[i];

    for i:=1 to len do
      inc(sum[rank[i]]);

    for i:=2 to m do
      sum[i]:=sum[i]+sum[i-1];

    for i:=len downto 1 do
      begin
        sa[sum[rank[i]]]:=i;
        dec(sum[rank[i]]);
      end;//此处求出的SA是1..len的一个全排列，在关键字完全相同时i较小的靠前

    trank[sa[1]]:=1;
    p:=1;
    for i:=2 to len do
      begin
        if rank[sa[i]]<>rank[sa[i-1]] then inc(p);
        trank[sa[i]]:=p;
      end;

    for i:=1 to len do rank[i]:=trank[i];
    m:=p;//m表示当前出现最高的rank
    j:=1;//j表示倍增的距离
    while j<len do
      begin
        fillchar(sum,sizeof(sum),0);
        p:=0;
     //接下来对第二关键字进行基数排序
        for i:=len-j+1 to len do
          begin
            inc(p);
            tsa[p]:=i;
          end;//这部分第二关键字为0

        for i:=1 to len do
          if sa[i]>j then
            begin
              inc(p);
              tsa[p]:=sa[i]-j;
            end;//枚举第二关键字sa[i]
        //tsa中按第二关键字排序，求出的是1..N的全排列，若第二关键字相同i较小的靠前

        for i:=1 to len do trank[i]:=rank[i];
        for i:=1 to len do inc(sum[trank[i]]);
        for i:=2 to m do sum[i]:=sum[i]+sum[i-1];
　　　　//按第一关键字排序，若第一关键字相同，在tsa中靠前的靠前
        for i:=len downto 1 do
          begin
            sa[sum[trank[tsa[i]]]]:=tsa[i];
            dec(sum[trank[tsa[i]]]);
          end;
      //至此，SA以维护

        trank[sa[1]]:=1;
        p:=1;
        for i:=2 to len do
         begin
           if (rank[sa[i]]<>rank[sa[i-1]]) or (rank[sa[i]+j]<>rank[sa[i-1]+j]) then inc(p);
           trank[sa[i]]:=p;
         end;
        for i:=1 to len do rank[i]:=trank[i];
        j:=j*2;
        m:=p;
      end;


  end;