后缀定义

“后缀i”代表以第i个字符开头的后缀，存储是用i代表字符串s的后缀s[i...n]

后缀数组是什么？

后缀数组（Suffix Array）主要关系到两个数组：sa 和 rk。

其中，sa[i] 表示将所有后缀排序后第 i 小的后缀的编号，也是所说的后缀数组，后文也称编号数组 sa；

(资料图片)

rk[i] 表示后缀 i 的排名，是重要的辅助数组，后文也称排名数组 rk。

这两个数组满足性质：sa[rk[i]]=rk[sa[i]]=i。

解释

后缀数组示例：

后缀数组怎么求？

O(n^2logn) 做法我相信这个做法大家还是能自己想到的：将盛有全部后缀字符串的数组进行 sort 排序，由于排序进行 O(n\log n) 次字符串比较，每次字符串比较要 O(n) 次字符比较，所以这个排序是 O(n^2\log n) 的时间复杂度。O(nlog^2n) 做法这个做法要用到倍增的思想。

首先对字符串 s 的所有长度为 1 的子串，即每个字符进行排序，得到排序后的编号数组 sa_1 和排名数组 rk_1。

倍增过程：

用两个长度为 1 的子串的排名，即 \(rk_1[i]\) 和 \(rk_1[i+1]\)，作为排序的第一第二关键字，就可以对字符串 s 的每个长度为 2 的子串：\(\{s[i\dots \min(i+1, n)]\ |\ i \in [1,\ n]\}\) 进行排序，得到 sa_2 和 rk_2；

之后用两个长度为 2 的子串的排名，即 rk_2[i] 和 rk_2[i+2]，作为排序的第一第二关键字，就可以对字符串 s 的每个长度为 4 的子串：\(\{s[i\dots \min(i+3, n)]\ |\ i \in [1,\ n]\}\) 进行排序，得到 sa_4 和 rk_4；

以此倍增，用长度为 w/2 的子串的排名，即 \(rk_{w/2}[i]\) 和 \(rk_{w/2}[i+w/2]\)，作为排序的第一第二关键字，就可以对字符串 s 的每个长度为 w 的子串 \(s[i\dots \min(i+w-1,\ n)]\) 进行排序，得到 sa_w 和 rk_w。其中，类似字母序排序规则，当 i+w>n 时，\(rk_w[i+w]\) 视为无穷小；

\(rk_w[i]\) 即是子串 \(s[i\dots i + w - 1]\) 的排名，这样当 w \geqslant n 时，得到的编号数组 sa_w，也就是我们需要的后缀数组。

#include using namespace std;const int N = 1000010;char s[N];int n, w, sa[N], rk[N << 1], oldrk[N << 1];// 为了防止访问 rk[i+w] 导致数组越界，开两倍数组。// 当然也可以在访问前判断是否越界，但直接开两倍数组方便一些。int main() {    int i, p;    scanf("%s", s + 1);    n = strlen(s + 1);    for (i = 1; i <= n; ++i)        sa[i] = i, rk[i] = s[i];    for (w = 1; w < n; w <<= 1) {        sort(sa + 1, sa + n + 1, [](int x, int y) {            return rk[x] == rk[y] ? rk[x + w] < rk[y + w] : rk[x] < rk[y];        }); // 这里用到了 lambda        memcpy(oldrk, rk, sizeof(rk));        // 由于计算 rk 的时候原来的 rk 会被覆盖，要先复制一份        for (p = 0, i = 1; i <= n; ++i) {            if (oldrk[sa[i]] == oldrk[sa[i - 1]] &&                oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) {                rk[sa[i]] = p;            } else {                rk[sa[i]] = ++p;            } // 若两个子串相同，它们对应的 rk 也需要相同，所以要去重        }    }    for (i = 1; i <= n; ++i)        printf("%d ", sa[i]);    return 0;}

责任编辑：Rex_10