后缀数组总结(旧)

这是一篇总结，所以不会讲什么细节。

以后可能会补上细节。可以参考这几位大佬的博客：后缀数组学习笔记、后缀数组：原理和实现，以及集训队爷的论文：后缀数组——处理字符串的有力工具、后缀数组。

模板

模板完全参照刘汝佳的蓝书，采用的是倍增的思想。~~D3算法写不来~~

有几处需要注意的地方在下面说明

#include <bits/stdc++.h>

#define MAXN 100000 + 50
using namespace std;
const int inf = 0x3f3f3f3f;
char s[MAXN];
int sa[MAXN], t[MAXN], t1[MAXN], c[MAXN], m = 256;
int r[MAXN];

void build_sa(int n) {
    int i, *x = t, *y = t1;
    for (i = 0; i < m; i++) c[i] = 0;
    for (i = 0; i < n; i++) c[x[i] = s[i]]++;
    for (i = 1; i < m; i++) c[i] += c[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;
    for (int k = 1; k <= n; k <<= 1) {
        int p = 0;
        for (i = n - k; i < n; i++) y[p++] = i;
        for (i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;
    
        for (i = 0; i < m; i++) c[i] = 0;
        for (i = 0; i < n; i++) c[x[y[i]]]++;
        for (i = 0; i < m; i++) c[i] += c[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
    
        swap(x, y);
        p = 1; x[sa[0]] = 0;
        for (i = 1; i < n; i++) x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1: p++;
        if (p >= n) break;
        m = p;
    } 
}
/*
int m;
int cmp_suffix(char* pat, int p) {
    return strncmp(pat, s + sa[p], m);
}

int find(char* p) {
    m = strlen(p);
    if (cmp_suffix(p, 0) < 0) return -1;
    if (cmp_suffix(p, n - 1) > 0) return -1;
    int L = 0, R = n - 1;
    while (R >= L) {
        int M = L + (R - L) / 2;
        int res = cmp_suffix(p, M);
        if (!res) return M;
        if (res < 0) R = M - 1; else L = M + 1;
    }
    return -1;
}
*/
int rnk[MAXN], height[MAXN];
void getHeight(int n) {
    int i, k = 0;
    for (i = 0; i < n; i++) rnk[sa[i]] = i;
    for (i = 0; i < n; i++) {
        if (k) k--;
        int j = sa[rnk[i] - 1];
        while (s[i + k] == s[j + k]) k++;
        height[rnk[i]] = k;
    }
}


int main() {
    scanf("%s", s);
    int n = strlen(s);
   // for (int i = 0; i < n; i++) r[i] = s[i] - 'a' + 1;

    build_sa(n + 1);
    getHeight(n + 1);
    for (int i = 1; i <= n; i++) printf("%d ", sa[i] + 1);
    //cout << n;

    cout << endl;
    for (int i = 1; i <= n; i++) printf("%d ", height[i]);
    return 0;
}

几处说明：

1.第17行，有大佬说这么操作会打乱基数排序的特性，实际操作时貌似并无大碍。

for (i = n - k; i < n; i++) y[p++] = i;

2.第27行，有大佬说+k的时候会爆空间。jiry_2大佬反驳说并不会，因为在越界的时候本身条件就不可能成立，跳过判断了。

for (i = 1; i < n; i++) x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1: p++;

3.一定不要忘记在字符串尾加上一个值，否则gg（我被这里RE了无数次）。白书上有强调（“$”字符）。具体表现为向两个函数传参时的n+1

就是这么多，简而言之，这是一份大家都说有问题的，但实际跑起来没有一点事的模板。

扩展

后缀数组如果只有一个SA那也没什么大作用，这时候引入两个辅助数组：height[]和rank[]。其中，$height[i] = LCP(sa[i - 1], sa[i])$ ，rank为名次数组，和sa两数组互为反函数，即：$rank[sa[i]] = i$ 。（SA数组：SA[名次]=地址，RANK数组：RANK[地址]=名次）

我们令$h[i] = height[rank[i]]$，足以发现一个性质：$h[i] \ge h[i - 1] - 1$。证明是显然的。

注意，这里的i是以在数组中的地址递增的，而不要想当然地以为是按照排序好的名次递增的。

LCP还有一种基于哈希值的算法。刘汝佳没有很详细的介绍，但从他的语气中，我们可以感觉到这个算法十分的exciting。

题目

按照惯例，上模板题：

1.UOJ#35

最裸的模板题，考后缀数组和LCP，用上面给的模板就能过。~~但是仍能RE一些弱鸡比如我~~

2.BZOJ1031

也是很裸的后缀数组的题目。看起来很叼的样子，其实考你是否背熟了模板。

后话

其实很多OI选手，对于后缀数组都是背诵流。真正理解精髓的不多。

是的，我也不理解精髓。

函数Build勉强读懂前面的部分，从27行那一坨就看的犯傻，问了问群里的大佬，大佬们告诉我这是在去重排序。

这告诉我们了什么？告诉了我们还是背诵流省事

以后有时间要回头磨透= = 别人的板子永远都是别人的，默写下来出问题的时候自己都不知道自己写了什么。

xD.