RenaMoe's Blog

念念不忘，必有回响

0%

板子 SA

发表于 更新于 分类于 ， Valine：

先贴个板子，总结有时间在再说

基数排序

\(O(n)\) 的排序是不是很诱人，桶排改进而已

1
2
3
4
5
6
7
8
9
10
inline void qsort() {
    for (int i = 1; i <= m; ++i)
        tax[i] = 0;
    for (int i = 1; i <= n; ++i)
        ++tax[rnk[i]];
    for (int i = 1; i <= m; ++i)
        tax[i] += tax[i-1];
    for (int i = n; i; --i)
        sa[tax[rnk[tp[i]]]--] = tp[i];
}

后缀排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
inline void get_SA() {
    for (int i = 1; i <= n; ++i)
        rnk[i] = s[i], tp[i] = i;
    m = 127, qsort();
    for (int w = 1, p = 0; w <= n && p < n; m = p, w <<= 1) {
        p = 0;
        for (int i = n - w + 1; i <= n; ++i)
            tp[++p] = i;
        for (int i = 1; i <= n; ++i)
            if (sa[i] > w)
                tp[++p] = sa[i] - w;
        qsort();
        swap(rnk, tp);
        rnk[sa[1]] = p = 1;
        for (int i = 2; i <= n; ++i)
            rnk[sa[i]] = (tp[sa[i]] == tp[sa[i-1]] && tp[sa[i]+w] == tp[sa[i-1]+w]) ? p : ++p;
    }
}

求 height 数组

1
2
3
4
5
6
7
8
inline void get_height() {
    for (int i = 1, k = 0, j; i <= n; ++i) {
        k = max(0, k - 1), j = sa[rnk[i]-1];
        while (s[i+k] == s[j+k])
            k++;
        ht[rnk[i]] = k;
    }
}