Acwing 2715. 后缀数组

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
int sa[MAXn + 10], rk[MAXn + 10], x[MAXn * 2 + 10], y[MAXn * 2 + 10], buc[MAXn + 10];
void EvaSaRk(int n, int m, char *str) {
    for (int i = 1; i <= n; ++i) ++buc[x[i] = str[i] - '0' + 1];
    for (int i = 2; i <= m; ++i) buc[i] += buc[i - 1];
    for (int i = n; i; --i) sa[buc[x[i]]--] = i;
    for (int half = 1; ; half <<= 1) {
        int cnty = 0;
        for (int i = n - half + 1; i <= n; ++i) y[++cnty] = i;
        for (int i = 1; i <= n; ++i) 
            if (sa[i] > half) y[++cnty] = sa[i] - half;
        memset(buc, 0, sizeof(buc));
        for (int i = 1; i <= n; ++i) ++buc[x[i]];
        for (int i = 2; i <= m; ++i) buc[i] += buc[i - 1];
        for (int i = n; i; --i) sa[buc[x[y[i]]]--] = y[i];
        swap(x, y);
        m = 0;
        for (int i = 1; i <= n; ++i) {
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + half] == y[sa[i - 1] + half]) ? m : ++m;
        }
        if (m == n) break;
    }
    for (int i = 1; i <= n; ++i) {
        rk[sa[i]] = i;
    }
}
int ht[MAXn + 10];
void EvaHt(int n, char *str) {
    for (int i = 1, k = 0, j; i <= n; ++i) {
        if (rk[i] == 1) continue;
        if (k) --k;
        j = sa[rk[i] - 1];
        while (str[i + k] == str[j + k]) ++k;
        ht[rk[i]] = k;
    }
}

EvaSaRk(n, 'z' - '0' + 1, str);
EvaHt(n, str);