UOJ35 后缀排序

发表于

  题意:造出一个字符串的后缀数组，将sa数组与height数组输出。

  这道题当然是一道后缀数组的模板。但是为了更高的效率，我们不用倍增法，而是使用SAM造出后缀树，再用后缀树造出后缀数组。
  关于后缀树的资料可以去网上找，在此不赘述。我们唯一需要知道的是，后缀树每一条边对应的字符串首字符都是互不相同的，仅仅依靠首字符就可以区别从一个节点伸出的所有边。
  首先，由于原串的SAM的next链接就是反串的后缀树，于是我们将原串的反串插入SAM，这样造出的后缀树就是原串的后缀树了。但是这样造出的仅仅是只有点和边的空后缀树，我们需要在上面添加信息。
  我们对于每个节点记录一个pos——代表其中最长串(反串前缀)在原串后缀中对应的首字符位置，方便以后造sa数组。我们还需要维护一个right数组，这个数组并不代表right集合。对于每个插入字符时为接纳新子串产生的节点(而非分裂出来的节点)，其right值=自身max值。而对于分裂出来的节点，其right值=该轮新产生节点的max。
  在造后缀树的时候，节点本身的right值-其next节点的max值=后缀树中next节点到该节点边的首字符在反串中的位置。更进一步地，将反串起始位置到该位置的子串翻转，就是这条边对应的字符串。其实这一点不难理解，结合一下定义就很容易明白，这里不多说了。
  将反串中的位置对应到原串上，找到那个字符作为边的首字符，我们就可以区分每条边，也就可以按照字典序遍历后缀树，依照每个节点的pos造出后缀数组了。
  上代码。

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i)
#define drep(i, l, r) for(int i = l, i##end = r; i >= i##end; --i)
#define erep(i, u) for(int i = head[u], v = E[i].v; i; i = E[i].nxt, v = E[i].v)
#define mp make_pair
#define ms(a, b) memset(a, b, sizeof a)
template<class T> inline bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline T& read(T& x)
{
	static char c; bool flag = 0;
	while(!isdigit(c = getchar())) if(c == '-') flag = 1;
	for(x = c ^ 48; isdigit(c = getchar()); x = (x << 3) + (x << 1) + (c ^ 48));
	if(flag) x = -x; return x;
}
const int maxn = 100010, SIZE = maxn << 2, SIGMA = 26;
int sa[maxn], sa_cur, rnk[maxn], height[maxn];
char s[maxn];
int n;
namespace SAM
{
    int ch[SIZE][SIGMA], next[SIZE], Max[SIZE], pos[SIZE], right[SIZE];
    int cur, last;
    void init() { cur = last = 1; }
    int New(int x) { Max[++cur] = x; return cur; }
    void extend(int c, int p)
    {
        int u = New(Max[last] + 1), v = last;
        pos[u] = p; right[u] = Max[u];
        for(; v && !ch[v][c]; v = next[v]) ch[v][c] = u;
        if(!v) next[u] = 1;
        else
        {
            int h = ch[v][c];
            if(Max[h] == Max[v] + 1) next[u] = h;
            else
            {
                int o = New(Max[v] + 1);
                right[o] = right[u];
                memcpy(ch[o], ch[h], sizeof ch[h]);
                next[o] = next[h];
                next[h] = next[u] = o;
                for(; v && ch[v][c] == h; v = next[v]) ch[v][c] = o;
            }
        }
        last = u;
    }
    namespace ST
    {
        struct edge
        {
            int u, v, w;
            int nxt;
        }E[SIZE];
        int head[SIZE], en;
        void ae(int i) { E[i].nxt = head[E[i].u]; head[E[i].u] = i; }
        void build_sa(int u)
        {
            if(pos[u]) sa[++sa_cur] = pos[u];
            erep(i, u) build_sa(v);
        }
        int sum[SIGMA], t[SIZE];
        void build_ST()
        {
            rep(i, 2, cur)
            {
                E[++en] = (edge) { next[i], i, s[n - (right[i] - Max[next[i]]) + 1] - 'a', 0 };
                ++sum[E[en].w];
            }
            rep(i, 1, SIGMA - 1) sum[i] += sum[i - 1];
            rep(i, 1, en) t[sum[E[i].w]--] = i;
            drep(i, en, 1) ae(t[i]);
        }
    }
    using namespace ST;
}
using namespace SAM;
void build_height()
{
    int j = 0;
    rep(i, 1, n) if(rnk[i] != n)
    {
        while(s[i + j] == s[sa[rnk[i] + 1] + j]) ++j;
        height[rnk[i]] = j; if(j) --j;
    }
}
int main()
{
    init();
    scanf("%s", s + 1); n = strlen(s + 1);
    drep(i, n, 1) extend(s[i] - 'a', i);
    build_ST();
    build_sa(1);
    rep(i, 1, n) rnk[sa[i]] = i;
    build_height();
    rep(i, 1, n) printf("%d ", sa[i]); puts("");
    rep(i, 1, n - 1) printf("%d ", height[i]); puts("");
    return 0;
}