BZOJ

BZOJ 1031

后缀数组模板题

传送门

直接把字符串复制一遍接在末尾，然后用裸的后缀数组处理完后按排名依次输出属于前一半的字符串


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
program bzoj_1031;
const maxl=100000;
var rank,sa,cnt,tsa,rank1,rank2:array[0..2*maxl]of longint;
    s:array[1..2*maxl]of char;
    n,i,p:longint;
begin
  n:=0;
  while not eoln do
  begin
    inc(n);
    read(s[n]);
  end;
  for i:=1 to n do s[n+i]:=s[i];
  n:=n<<1;
  for i:=0 to 255 do cnt[i]:=0;
  for i:=1 to n do inc(cnt[ord(s[i])]);
  for i:=1 to 255 do inc(cnt[i],cnt[i-1]);
  for i:=1 to n do rank[i]:=cnt[ord(s[i])];
  p:=1;
  while p<n do
  begin
    for i:=1 to n do
    begin
      rank1[i]:=rank[i];
      if i+p<=n then rank2[i]:=rank[i+p] else rank2[i]:=0;
    end;
    for i:=0 to n do cnt[i]:=0;
    for i:=1 to n do inc(cnt[rank2[i]]);
    for i:=1 to n do inc(cnt[i],cnt[i-1]);
    for i:=n downto 1 do
    begin
      tsa[cnt[rank2[i]]]:=i;
      dec(cnt[rank2[i]]);
    end;
    for i:=0 to n do cnt[i]:=0;
    for i:=1 to n do inc(cnt[rank1[i]]);
    for i:=1 to n do inc(cnt[i],cnt[i-1]);
    for i:=n downto 1 do
    begin
      sa[cnt[rank1[tsa[i]]]]:=tsa[i];
      dec(cnt[rank1[tsa[i]]]);
    end;
    rank[sa[1]]:=1;
    for i:=2 to n do
    begin
      rank[sa[i]]:=rank[sa[i-1]];
      if (rank1[sa[i]]<>rank1[sa[i-1]])or(rank2[sa[i]]<>rank2[sa[i-1]]) then inc(rank[sa[i]]);
    end;
    p:=p<<1;
  end;
  for i:=1 to n do if sa[i]<=n>>1 then write(s[sa[i]+n>>1-1]);
  writeln;
end.