求height数组

  procedure getheight;

  var

   i,po1,po2:longint;

    begin

      for i:= to len do

        begin

          if k> then k:=k-;

          po1:=i;po2:=sa[rank[i]-];

          while (a[po1+k]=a[po2+k]) and (po1+k<=len) and (po2+k<=len) do

            inc(k);

          height[i]:=k;

        end;

    end;

其中height[i]表示suffix（i）与suffix(sa[rank[i]-1])的最长公共前缀

____________________________________________________

c++

void getheight(){

      int k=;

      int po1,po2;

      for (int i=;i<=n;i++){

          po1=i,po2=sa[rank[i]-];

          if (k) k--;

          while ((st[po1+k]==st[po2+k])&&(po1+k<=len)&&(po2+k<=len))

          k++;

          height[rank[i]-]=k;

      }

  }

其中height[i]表示rank[i]+1与rank[i]的最长公共前缀