后缀数组

简介

后缀数组所做的最直接的就是将一个字符串的所有后缀排了个序

所以我们得到了两个数组，$sa_i$ 表示排名为 $i$ 的后缀是哪一个，$rk_i$ 表示 $suf_i$ 的排名

性质

令 $lcp(l,r)$ 为 $sa_l$ 和 $sa_r$ 的最长公共前缀

1. $lcp(l,r)=min\lbrace lcp(l,i),lcp(i,r)\rbrace$，其中 $i\in[l,r]$，注意到这里只需要枚举任意一个 $i$ 即可

   证明：

   令 $p=min\lbrace lcp(l,i),lcp(i,r)\rbrace ,u=sa_l,v=sa_r,w=sa_i$

   由于 $u$ 和 $w$ 的前 $p$ 位相同，$v$ 和 $w$ 的前 $p$ 位相同

   所以 $u$ 和 $v$ 的 $lcp$ 至少为 $p$

   假设 $u$ 和 $v$ 的 $lcp>p$，不妨设其为 $q=p+1$

   我们知道 $u[q]\neq w[q],v[q] \neq w[q]$，并且 $w[q]\ge u[q],v[q]\ge w[q]$

   那么 $w[q]$ 只能是 $>u[q]$，且 $v[q]$ 只能是 $>w[q]$，所以 $u[q]$ 不可能等于 $v[q]$

2. $lcp(l,r)=min_{i=l}^{r-1}lcp(i,i+1)$

   证明：

   注意到 $lcp(l,r)=min\lbrace lcp(l,l+1),lcp(l+1,r)\rbrace$

   递归运算即可即证

根据 $sa$ 和 $rk$ 这两个数组，我们还能得到另外一个东西

我们令 $H_i$ 表示 $sa_i$ 和 $sa_{i-1}$ 的最长公共前缀的长度

1. $H_{rk_{i}}\ge H_{rk_{i-1}}-1$

   证明：

   令 $suf_k$ 为排名正好在 $suf_{i-1}$ 前一个的后缀，那么它们的公共前缀的长度就是 $H_{rk_{i-1}}$

   注意到 $suf_{k+1}$ 的排名一定在 $suf_i$ 之前，而 $suf_{k+1}$ 和 $suf_i$ 的最长公共前缀至少是 $H_{rk_{i-1}}-1$

   所以 $H_{rk_{i}}\ge H_{rk_{i-1}}-1$

2. $suf_l$ 和 $suf_r$ 的最长公共前缀为 $\min_{i=rk_x+1}^{rk_y}H_i$

3. $min_{i=1}^{k-1}lcp(i,k)=H_k$

   也就是固定一个位置之后，另个位置向某一方向移动时最长公共前缀的长度减少

模板

int tax[maxn], tp[maxn], sa[maxn], rk[maxn], M = 255;
void rsort() {
    // tp[i] 表示排序时第二关键字为 i 的后缀是什么
    // rsort 的实际作用就是按照 rk[i] 为第一关键字，tp[i] 为第二关键字从小到大排序
    for (int i = 0; i <= M; ++i) tax[i] = 0;
    for (int i = 1; i <= n; ++i) ++tax[rk[i]];
    for (int i = 1; i <= M; ++i) tax[i] += tax[i - 1];
    for (int i = n; i; --i) sa[tax[rk[tp[i]]]--] = tp[i];
}

int H[maxn]; // cnt 表示不同的 rk[i] 有多少个，当 c1 == n 时，排序完毕
void init_sa() {
    if (n == 1) return sa[1] = rk[1] = 1, void(); int cnt = 1; 
    for (int i = 1; i <= n; ++i) rk[i] = s[i], tp[i] = i; rsort();
    for (int k = 1; k < n; k *= 2) {
        if (cnt == n) break; M = cnt; cnt = 0;
        for (int i = n - k + 1; i <= n; ++i) tp[++cnt] = i;
        for (int i = 1; i <= n; ++i) if (sa[i] > k) tp[++cnt] = sa[i] - k;
        rsort(); swap(rk, tp); rk[sa[1]] = cnt = 1;
        // 这时候的 tp 变成了上一轮的 rk，cnt 是计数器同时是不同的 rk[i] 的个数
        for (int i = 2; i <= n; ++i) {
            if (tp[sa[i - 1]] != tp[sa[i]] || tp[sa[i - 1] + k] != tp[sa[i] + k]) ++cnt;
            // 如果排名为 i - 1 和排名为 i 的串的前 k 位相同，并且前 2k 位也相同，那么这两个串的排名就暂时相同了
            rk[sa[i]] = cnt;
        }
    } int lcp = 0;
    for (int i = 1; i <= n; ++i) {
        if (lcp) --lcp;
        int j = sa[rk[i] - 1];
        while (s[j + lcp] == s[i + lcp]) ++lcp;
        H[rk[i]] = lcp;
    } 
}

应用

先给几个定义：

重复子串：对于一个串，如果它的一个子串在原串中出现出现至少两次，则称这个子串是一个重复子串

可重叠子串：只这个子串在原串中的出现位置可以重叠

1. 可重叠最长重复子串

   问题：求可重叠最长重复子串的长度

   解法：利用后缀数组将所有后缀按照字典序排序后，我们考虑加入一个后缀的贡献

   容易得到加入 $sa_i$，那么它与前面所有后缀的 $lcp$ 就是 $H_i$，那么它的贡献就是 $H_i$

   所以答案就是 $H$ 的最大值，时间复杂度 $O(n\log n)$

2. 可重叠重复子串计数

   问题：求有多少本质不同的子串出现至少两次

   解法：同之前将所有后缀按照字典序排序，考虑加入一个后缀的贡献

   我们知道 $sa_i$ 贡献的重复的子串为 $H_i$，那么我们现在要求的就是 $H_i$ 中只出现过一次的前缀个数

   我们考虑对于 $sa_{i-1}$，它贡献的只出现过一次的串为 $n-sa_{i-1}+1-H_{i-1}$

   而这些与 $H_i$ 有交集的只有 $max\lbrace H_i-H_{i-1},0\rbrace$

   所有答案就是 $\sum_{i=1}^nmax\lbrace H_i-H_{i-1},0\rbrace$，时间复杂度 $O(n\log n)$

3. 不可重叠最长重复子串

   问题：求不可重叠最长重复子串的长度

   解法：首先我们考虑二分答案 $x$，然后我们考虑固定一个 $sa_i$，然后去前面找即 $j<i$，如果存在这么一个子串，那一定存在一个 $sa_j$ 满足 $|sa_i-sa_j+1|\ge x\wedge lcp(j,i)\ge x$

   注意到 $lcp$ 的性质，如果存在这么一个 $j$，那么一定有 $min_{k=j+1}^i H_k\ge x$

   这个东西二分之后可以轻松 $O(n)$ 判断，时间复杂度 $O(n\log n)$

4. 可重叠 $k$ 次最长子串

   问题：求可重叠的出现了至少 $k$ 次的最长子串的长度

   解法：我们仍然考虑二分答案 $x$

   我们考虑如果有一个满足条件的子串出现了 $k$ 次，那么我们把这 $k$ 个起始位置拿出来，这些位置的 $lcp$ 显然要大于等于 $x$

   那么我们相当于二分只有需要判断是否存在一个长度为 $k-1$ 的区间满足区间最小值大于等于 $x$

   显然可以单调队列维护，然后我们甚至可以将二分去掉，时间复杂度 $O(n\log n)$

5. 本质不同的子串的个数

   问题：求本质不同的子串个数

   解法：将所有后缀按照字典序排序，考虑加入一个后缀的贡献

   每次新加进来的一个后缀的贡献显然是 $n-sa_i+1$，但是与前面的所有后缀重复的前缀有 $H_i$ 个，所以它的总贡献就是 $n-sa_i+1-H_i$

   答案即为 $\sum_{i=1}^nn-sa_i+1-H_i$，时间复杂度 $O(n\log n)$

6. 重复出现次数最多的连续重复子串

   我们考虑枚举连续重复子串的长度 $l$，然后我们将串分成 $\lfloor\frac{n}{l}\rfloor$ 块

   求出相邻两块的 $lcp$ 的长度 $k$，那么出现次数为 $k/l+1$

   注意还要检查一下块前面的一部分是否可以加进去

   时间复杂度为 $O(n\log n)$

例题

1. 简要题意：给定一个长度为 $n$ 的字符串，求其本质不同的子串个数

   $n\le 10^5$

   简要题解：本质不同子串个数

   Luogu P2408 不同子串个数

2. 简要题意：给定一个长度为 $n$ 的字符串和 $k$，求长度最长的一个子串，满足这个子串至少出现了 $k$ 次

   $n\le 2\times 10^4$

   简要题解：可重叠 $k$ 次最长子串

   Luogu P2852 [USACO06DEC]Milk Patterns G

3. 简要题意：给定一个长度为 $n$ 的字符串 $S$，求 $\sum_{1\le i<j\le n}len(suf(S,i))+len(suf(S,j))-2lcp(suf(S,i),suf(S,j))$

   $n\le 5\times 10^5$

   简要题解：前面那个东西显然是 $\frac{(n-1)n(n+1)}{2}$，后面那个东西就是 $\sum_{1\le i<j\le n}lcp(i,j)$，换句话就是 $H$ 的所有子区间的 $min$ 的和，这个可以用单调栈来求

   Luogu P4248 [AHOI2013]差异

4. 简要题意：给定一个字符串和 $m$ 次询问，每次询问给定两个集合 $A$ 和 $B$，求 $\sum_{i\in A,j\in B}lcp(suf(S,i),suf(S,j))$

   $n,m,\sum |A|,\sum |B|\le 2\times 10^5$

   简要题解：首先将 $A$ 和 $B$ 分别按照 $rk$ 排序，将 $lcp$ 的询问转换成区间求 $min$

   下面只考虑 $b_ja_i$ 的情况可以使用相同的方法处理，相等的单独处理即可

   我们用类似扫描线的东西，用数据结构维护所有左端点对于当前右端点的答案的和

   右端点移动相当于全局取 $min$，单点插入，左端点移动相当于单点插入，所以我们可以使用权值线段树

   时间复杂度 $O(n\log n)$

   CF 1073G Yet Another LCP Problem

5. 简要题意：给定三个字符串 $A,B,C$，求对于所有 $l$，有多少个数对 $(a,b,c)$，满足 $A[a\cdots a+l-1]=B[b\cdots b+l-1]=C[c\cdots c+l-1]$

   $|A|+|B|+|C|\le 3\times 10^5$

   简要题解：我们考虑后缀数组，将这三个字符串用特殊字符连起来后，我们枚举 $l$，将 $H_i\ge l$ 的 $i$ 和 $i-1$ 连起来，然后对于一个连续区间，其贡献就是属于第一个字符串的数量乘上第二个字符串的数量乘上第三个字符串的数量，我们发现倒叙枚举 $l$ 只有合并，可以用并查集维护，时间复杂度 $O(n\log n)$

   CF 452E Three strings

6. 简要题意：给定一个长度为 $n$ 的字符串和 $m$ 次询问，每次询问给定四个参数 $a,b,c,d$，求 $S[a\cdots b]$ 的所有子串和 $S[c\cdots d]$ 的 $lcp$

   $n,m\le 10^5$

   简要题解：首先考虑二分答案 $x$，然后我们考虑后缀数组，相当于求是否存在 $[a,b-x+1]$ 之间的后缀，满足排序后这个后缀到 $c$ 的区间最小值大于等于 $x$

   我们考虑先二分出 $c$ 周围的最小值大于 $x$ 的区间 $[l,r]$，那么就相当于二维区间查询，主席树显然可以胜任

   时间复杂度 $O(n\log^2n)$

   Luogu P4094 [HEOI2016/TJOI2016]字符串