1. 首页
  2. Let's OI!
  3. 正文

UOJ35后缀排序【后缀数组模板】

  • 内容
  • 评论
  • 相关

顾名思义啦，后缀数组的模板

题目：

这是一道模板题。

读入一个长度为 n 的由小写英文字母组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 1 到 n。

除此之外为了进一步证明你确实有给后缀排序的超能力，请另外输出 n−1 个整数分别表示排序后相邻后缀的最长公共前缀的长度。

总之题目输出的要求都是后缀数组的几个数组的定义啦，第一行是SA数组，第二行就是height数组，套模板就可以了，关于后缀数组NOCOW有一个很好的讲解。

 

代码是参考NOCOW的，翻译成了P，注意C++字符串下标从0开始

var
  s:ansistring;
  rank,trank,sa,tsa,sum,h:array[0..100000]of longint;
  i,j,k,n,m,p:longint;
procedure sort(j:longint);
var
  i:longint;
begin
  fillchar(sum,sizeof(sum),0);
  for i:=1 to n do inc(sum[rank[i+j]]);
  for i:=1 to n do inc(sum[i],sum[i-1]);
  for i:=n downto 1 do
  begin
    tsa[sum[rank[i+j]]]:=i;
    dec(sum[rank[i+j]]);
  end;
  fillchar(sum,sizeof(sum),0);
  for i:=1 to n do inc(sum[rank[i]]);
  for i:=2 to n do inc(sum[i],sum[i-1]);
  for i:=n downto 1 do
  begin
    sa[sum[rank[tsa[i]]]]:=tsa[i];
    dec(sum[rank[tsa[i]]]);
  end;
end;
begin
  readln(s);
  n:=length(s);
  for i:=1 to n do inc(sum[ord(s[i])-96]);
  for i:=2 to 26 do inc(sum[i],sum[i-1]);
  for i:=n downto 1 do
  begin
    sa[sum[ord(s[i])-96]]:=i;
    dec(sum[ord(s[i])-96]);
  end;
  rank[sa[1]]:=1;
  p:=1;
  for i:=2 to n do
  begin
    if s[sa[i]]<>s[sa[i-1]] then inc(p);
    rank[sa[i]]:=p;
  end;
  j:=1;
  while j<n do
  begin
    sort(j);
    trank[sa[1]]:=1;
    p:=1;
    for i:=2 to n 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 n do
    rank[i]:=trank[i];
    j:=j*2;
  end;
  j:=0;
  for i:=1 to n do
  begin
    if rank[i]=1 then continue;
    while s[i+j]=s[sa[rank[i]-1]+j] do inc(j);
    h[rank[i]]:=j;
    if j>0 then dec(j);
  end;
  for i:=1 to n do
  write(sa[i],' ');
  writeln;
  for i:=2 to n do
  write(h[i],' ');
  writeln;
end.
 
</n>

评论

0条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。