相关定义及其证明

sa 后缀数组 suffix array

保存 $0 \sim n-1$ 的全排列，含义是把所有后缀按字典序排序后，后缀在原串中的位置。$suffix(sa[i]) < suffix(sa[i + 1])$

$sa[,]$ 记录位置，即“排第i的后缀是谁”。

rk 名次数组 rank array

保存 $0 \sim n-1$ 的全排列，$rk[i]$ 的含义是 $suffix(i)$ 在所有后缀中按字典序排序的名次。

$rk[,]$ 记录排名，即“第以第i个字符起始的后缀子串在所有后缀子串中排第几”。

sa 与 rk 的关系

$sa[,]$ 与 $rk[,]$ 是一一对应的关系，且互为逆运算。于是

可用 $rk[,]$ 推导 $sa[,]$： for (int i = 0; i < n; ++i) sa[rk[i]] = i;

可用 $sa[,]$ 推导 $rk[,]$： for (int i = 0; i < n; ++i) rk[sa[i]] = i;

LCP 最长公共前缀

LCP 即 Longest Common Prefix，最长公共前缀。

记 $LCP(i, j)$ 为 $suffix(sa[i])$ 与 $suffix(sa[j])$ 的最长公共前缀长度，即排序后第 $i$ 个后缀与第 $j$ 个后缀的最长公共前缀长度

LCP Lemma (LCP引理)

若 $0 \lt i \lt j \lt k \le n-1$，则 $LCP(i, k) = min{LCP(i, j),,LCP(j, k)}$。

证明：

设 $p=min{LCP(i, j), LCP(j, k)}$ ，则 $LCP(i, j) \ge p ,;LCP(j, k) \ge p$。

又设 $suffix(sa[i])=u,;suffix(sa[j])=v,;suffix(sa[k])=w$ ①。

我们记 $a=_{len}b$表示字符串 $a$ 长度为 $len$ 的前缀与字符串 $b$ 的长度为 $len$ 的前缀相等。

则由 $u={LCP(i,j)}v$ 可得 $u={p}v, ; v=_{p}w$ 。

于是可得 $u=_{p}w$。即 $LCP(i, k) \ge p = min{LCP(i, j),,LCP(j, k)}$。

现在我们再证 $LCP(i,k) \gt p$ 是不可能的。

又设存在一个 $q \gt p$，$LCP(i, k) = q$。

则可得 $u[i] = w[i]$ 对任意 $i \in [1, q]$ 均成立。由于 $q \gt p$，所以上式中的一个是 $u[p+1] = w[p+1]$。

由 ① 得 $u[p+1] \leq v[p+1] \leq w[p+1]$。结合上一行得 $u[p+1]=v[p+1]=w[p+1]$。

而 $p=min{LCP(i, j), LCP(j, k)}$，即 $u[p+1] \neq v[p+1]$ 或 $v[p+1] \ne w[p+1]$。

出现矛盾，故不存在 $q$ ，使得假设 $LCP(i, k) = q \gt p$ 成立。即得 $LCP(i, k) \le p$。

故得 $LCP(i, k) \ge p$ 且 $LCP(i, k) \le p$。

最后 $LCP(i, k) = min{LCP(i, j), LCP(j, k)}$。

LCP Theorem(LCP定理)

若 $i \lt j$ 则 $LCP(i, j) = min{LCP(k - 1, k)},;i \lt k \le j$

证明：由 LCP Lemma 与数学归纳法可得。

height 高度数组

$height[,]$ 是一个辅助数组，和最长公共前缀 (LCP) 相关。

令 $height[i]=LCP(i-1,i),;1 \lt i \le n$ ，即 $suffix(sa[i-1])$ 与 $suffix(sa[i])$ 的最长公共前缀长度。

为了描述方便，记 $h[i]$ 为 $height[rank[i]]$ ，即后缀 $suffix(i)$ 与 $suffix(sa[rank[i]-1])$ 的LCP长度。

有一个很重要的性质可以让我们在 $O(N)$ 的时间内求得 $height[]$ 数组：$h[i] \ge h[i-1] - 1$ 。

证明：

设 $suffix(k)$ 是排在 $suffix(i-1)$ 前一名的后缀，则它们的LCP长度为 $h[i-1]$。两者都去掉第一个字符，得到 $suffix(k+1)$ 与 $suffix(i)$ 。

① 若 $h[i-1] \le 1$ ，即 $h[i-1]-1 \le 0$ ，则 $h[i] \ge h[i-1] - 1$ 显然成立。

② 若 $h[i-1] \gt 1$ ，则在上面去掉第一个字符的过程中是去掉的两者LCP中的第一个字符，那么 $suffix(k+1)$ 与 $suffix(i)$ 的LCP长度就至少为 $h[i] \ge [h-1]-1$ 。

故 $h[i] \ge h[i-1]-1$ 得证。

倍增+基数排序 求 sa, rk, height 三数组

个人模板，供参考。设字符串长度为 $N$，则下面代码求三数组的复杂度为 $O(N;logN)$。

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

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1e6 + 50;

char s[N];
int sa[N], rk[N], cnt[N], height[N], t1[N], t2[N];

void calcSA(char *s, int n) {
    int m = 256;
    int i, *x = t1, *y = t2;
    for (i = 1; i <= m; ++i) cnt[i] = 0;
    for (i = 1; i <= n; ++i) ++cnt[x[i] = s[i]];
    for (i = 2; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[x[i]]--] = i;
    for (int k = 1; k <= n; k <<= 1) {
        int p = 0;
        for (i = n - k + 1; i <= n; ++i) y[++p] = i;
        for (i = 1; i <= n; ++i)
            if (sa[i] > k) y[++p] = sa[i] - k;
        for (i = 1; i <= m; ++i) cnt[i] = 0;
        for (i = 1; i <= n; ++i) ++cnt[x[i]];
        for (i = 2; i <= m; ++i) cnt[i] += cnt[i - 1];
        for (i = n; i >= 1; --i) sa[cnt[x[y[i]]]--] = y[i];
        swap(x, y);
        x[sa[1]] = 1;
        p = 1;
        for (i = 2; i <= n; ++i)
            x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k]) ? p : ++p;
        if (p >= n) break;
        m = p;
    }
    for (i = 1; i <= n; ++i) rk[sa[i]] = i;
    for (int i = 1, k = 0; i <= n; ++i) {
        if (rk[i] == 1) {
            height[rk[i]] = 0;
        } else {
            if (k) --k;
            int j = sa[rk[i] - 1];
            while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++k;
            height[rk[i]] = k;
        }
    }
}

int main() {
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    calcSA(s, len);
    for (int i = 1; i <= len; ++i) printf("%d ", sa[i]);
    return 0;
}

后记

https://www.cnblogs.com/ECJTUACM-873284962/p/6618870.html

https://blog.csdn.net/qq_37774171/article/details/81776029

从上两文中做了一些参考，但部分证明感觉并不浅显易懂，在加以个人理解后最后形成此文。

传送门

此题让我们实现一个LRU的模板类。本题较简便且高效的写法是维护一个std::list和一个std::unordered_map。

std::list 与 std::unordered_map 中存放的内容

std::list中存放各key，类型为K。链表中各键码存放的顺序是按照访问顺序存放的。

std::unordered_map中以key为第一维，第二维为一个pair，其first和second分别为：

first: 该key对应的value。

second:该key在std::list中的迭代器方便访问。

为方便，下面用“链表”来指代std::list，用“哈希表”来指代std::unordered_map。

各操作实现

insert操作：用哈希表判断该键是否已经存在。若存在，先在链表中删除该key，然后再新加一个该key到链表尾部，并更新在哈希表中的value和链表的迭代器。若不存在，则直接加至链表尾部，并在哈希表中插入该key，伴随着对应的value和链表迭代器。

get操作：直接从哈希表中获得其value即可。代码实现未检测该key是否存在，严谨来说应该加上异常处理。

contains操作：直接在哈希表中查询是否存在该key即可。

vis操作：用哈希表判断该键是否存在。若不存在，则本操作无效。否则，将该键从链表中删除，然后再将其加至链表尾部，并更新哈希表中对应链表迭代器。

pop操作：判断是否整个容器已经为空。若为空，则本操作无效。否则，将链表头部元素从链表中删除，并在哈希表中删除对应键值信息。

remove操作：用哈希表判断该键是否存在。若不存在，则本操作无效。否则，将该键从链表中删除，并在哈希表中删除对应键值信息。

empty操作：哈希表或链表判空即可。

size操作：取哈希表或链表大小即可。

clear操作：清空哈希表和链表即可。

时间复杂度

各操作基于对链表和哈希表的修改。期望复杂度均为$O(1)$。