字符串基础

Alex_Wei · 2023-04-08 22:56:50 · 算法·理论

推荐在 cnblogs 阅读。

前言

几乎所有字符串算法都存在一个共性：基于所求信息的特殊性质与已经求出的信息，使用增量法与势能分析求得所有信息。这体现了动态规划思想。

Manacher 很好地证明了这一点：它维护所求得的最右回文子串的回文中心 d 与回文半径 r，利用回文性质通过均摊右端点移动距离在线性时间内求出以每个位置为中心的最长回文半径。

SA，KMP，Z 与 SAM 等常见字符串算法无不遵循这一规律。读者在阅读时注意体会这种思想，笔者认为其对于提升解决问题的能力有很大帮助。

定义与记号

约定

• 文章使用打字机字体 texttt 描述一个字符串的具体内容，例如 s = \texttt {alexwei}。
• 无歧义时，n 表示当前描述的字符串的长度。在字符串两侧加上 | 表示长度。
• 当下标 i 不在 [1, n] 范围内时，对应位置的字符 s_i 视为空字符。

基本定义

• 字符集：字符集 可以是任何具有全序关系的集合 \Sigma，即 \Sigma 中任意两个不同元素 x, y \in \Sigma（x\neq y）可比较大小。除非特殊规定，一般按字母表顺序或数码大小比较元素。
• 字符：字符集 \Sigma 中的元素称为 字符。s_i 或 s[i] 表示 s 的第 i 个字符。
• 空串：不含任何字符的字符串称为 空串，记作 \epsilon，|\epsilon| = 0。空串之于字符串类似空集之于集合。
• 子串：由 s 在开头或末尾删去若干字符得到的字符串称为 s 的 子串。s 本身和空串均为 s 的子串。s[l, r] 或 s_{l, r} 表示 s 位置 l\sim r 上的字符连接而成的子串，当 l > r 时为空串。
• 反串：翻转 s 得到 s 的 反串，记作 s ^ R。
• 回文串：s = s ^ R 的串称为 回文串。特别地，空串是回文串。
• 拼接：s + t 表示将 t 拼接在 s 后。

前后缀相关

• 前缀：在 s 末尾删去若干字符得到的字符串称为 s 的 前缀，形如 s[1, i]（0\leq i \leq n），记作 pre_i。s 本身和空串均为 s 的前缀。
• 后缀：在 s 开头删去若干字符得到的字符串称为 s 的 后缀，形如 s[i, n]（1\leq i \leq n + 1），记作 suf_i。s 本身和空串均为 s 的后缀。
• 真前 / 后缀：真前缀 表示非原串前缀，真后缀 同理。
• 最长公共前缀：\mathrm{lcp}(s, t) 表示 s 和 t 的 最长公共前缀（Longest Common Prefix），即最长的 u 使得 u 同时为 s 和 t 的前缀。最长公共后缀（Longest Common Suffix）同理。
• 字典序：定义空字符小于任何字符。称 s 的 字典序 小于 t 当且仅当去掉 \mathrm{lcp}(s, t) 后，s 的第一个字符小于 t 的第一个字符。等价于以第 i 个字符作为第 i 关键字比较。

匹配相关

• 出现位置：若 s[p - |t| + 1, p] = t，则称 t 在 s 中以位置 p 出现。t 在 s 中的 出现位置 等于 t 的最后一个字符在 s 中的对应位置。例如，若 s = \texttt{abcbabc}，t = \texttt{abc}，则 t 在 s 中的所有出现位置为 \{3, 7\}。

• 匹配：称字 t 匹配 s 当且仅当 t 在 s 中出现。

• 模式串（单词）：用于匹配的字符串称为 模式串，相当于题目给定的 单词。

• 字典：题目给定的所有模式串的集合称为 字典。

• 文本串：被匹配的字符串称为 文本串。

• 分清模式串和文本串的定义：用 t 匹配 s 即求 t 在 s 中的所有出现位置，t 是 用于匹配的串，称为模式串（模式串是我们要寻找的模式，是子串）；s 是 被匹配的串，称为文本串（文本串相当于给出的文本，是主串）。

1. Manacher 算法

Manacher 在所有字符串算法中理解起来相对容易，学习它有助于理解 Z 算法。

Manacher 在 NOI 大纲里是 8 级算法。

1.1 相关定义

根据回文串的定义，我们发现奇回文串和偶回文串本质不同。当 n 为奇数时，其 回文中心 为它最中间的位置 \frac {n + 1} 2；当 n 为偶数时，其回文中心为位置 mid 与 mid + 1 之间的空隙，其中 mid = \frac n 2。

此外，定义回文串 s 的 回文半径 为其开头到回文中心形成的字符串长度。当 |s| 是奇数时，s 的回文半径为 \frac {n + 1} 2；当 n 是偶数时，s 的回文半径为 \frac n 2。

容易发现对于 s 的某个回文子串 s[l, r]，若 l < r，则 s[l + 1, r - 1] 回文。因此，若 x 是 i 的回文半径，则任何小于等于 x 的正整数均为 i 的回文半径。因此，考虑一个回文中心：

• 当它是下标 i 时，存在阈值 R 满足当 0\leq j < R 时 s[i - j, i + j] 回文，R 称为以位置 i 为回文中心的 最长回文半径 R_i。它可以理解为以 i 为回文中心的回文子串数。
• 同理，当它是 i 与 i + 1 之间的空隙时，存在阈值 R 满足当 0\leq j < R 时，s[i - j, i + 1 + j] 回文。

1.2 统一奇偶回文子串

为避免分类讨论，我们尝试将所有偶回文子串转化为奇回文子串。

容易发现，若将所有空隙视作一种独立的 分隔字符，则偶回文子串可视为以对应分隔符为回文中心的奇回文子串。例如 \texttt {abbbba}，若将空隙视为字符 \texttt c，则原串变为新串 \texttt {cacbcbcbcbcac}。

考虑原串偶回文子串在新串上的形态。偶回文子串 \texttt {bb} 对应新串 \texttt {cbcbc}，\texttt {abbbba} 对应新串 \texttt {cacbcbcbcbcac}。手动模拟可知若某分隔符在新串上的最长回文半径为 R_i（一定是奇数），则它对应的原串最长回文子串长度为 R_i - 1。

考虑原串奇回文子串在新串上的形态。奇回文子串 \texttt{bbb} 对应新串 \texttt {cbcbcbc}。手动模拟可知若某原串下标在新串上的最长回文半径为 R_i（一定是偶数），则它对应的原串最长回文半径为 \frac {R_i} 2，最长回文子串长度同样为 R_i - 1。

这样，我们统一了奇回文串和偶回文串从新串转回原串的过程，有效减少了根据最长回文半径 R_i 求解问题的细节，并得到结论：新串的 R_i 表示原串以对应下标或空隙为中心的最长回文子串长度加 1。

1.3 算法介绍

Manacher 算法可以求出以每个位置 i 为回文中心的最长回文半径 R_i。当然，也可以求出以每个空隙为回文中心的最长回文半径。这种情况已经转化为前者。

首先将 s 的所有字符之间插入相同分隔符，包括头尾，然后在整个字符串头尾插入另外两种不同的分隔符，以防止越界。

朴素想法是对每个回文中心 i，从 1 开始从小到大暴力枚举 R_i。很遗憾，全 \texttt {a} 串就可以将复杂度卡成 \mathcal{O}(n ^ 2)。具体复杂度是 n 加上 s 的回文子串数量，出现在不同位置的相等子串 算多个。

只需加上一些优化即可将复杂度变为 \mathcal{O}(n)。

回顾朴素暴力，在从 R_i = 1 开始枚举的过程中，我们浪费了很多由回文性质带来的有用信息。考虑回文中心 c 及其右端点 r = c + R_c - 1，若当前希望求出 R_i（c < i） 且满足 i \leq r，则我们完全可以利用 2c - i 处已经求得的 R_{2c - i} 的信息。

具体地，在 c 的最长回文半径范围内，因为 c < i \leq r，所以 2c - i 和 i 在该范围内对称。也就是说，在 [c - R_c + 1, c + R_c - 1] 范围内，以 2c - i 为对称中心的回文串也是以 i 为对称中心的回文串。因此，我们得出 R_i \geq \min(r - i + 1, R_{2c - i})。

如上图，因为黄色部分回文，所以对于以 2c - i 为回文中心且落在黄色部分的回文串（橙色部分），一定也在 i 处出现。

因此，考虑维护已经计算过的所有回文中心对应的最长回文子串的右端点的最大值 r = \max_{p = 1} ^ {i - 1} p + R_p - 1 以及对应回文中心 c。

对于当前位置 i，若 r < i，则从 0 开始枚举求得 R_i。此时每次扩展均使得 r 向右移动 1。

否则 i\leq r，利用回文性质和已经求出的信息，先将 R_i 赋值为 \min(r - i + 1, R_{2c - i})，再逐位扩展：

• 若 R_{2c - i} < r - i + 1，则 R_i 就等于 R_{2c - i}。否则根据对称性 R_{2c - i} 可以更大，与其最大性矛盾。
• 否则 R_i 被初始化为 r - i + 1，使得每次扩展都会将 r 向右移动 1。

综上，时间复杂度线性。

模板题 P3805 代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 2.2e7 + 5;
int n, m, ans, R[N];
char s[N], t[N];
int main() {
  scanf("%s", s + 1), n = strlen(s + 1);
  t[0] = '!', t[m = 1] = '@';
  for(int i = 1; i <= n; i++) t[++m] = s[i], t[++m] = '@'; // 间隔插入字符.
  t[++m] = '#';
  for(int i = 1, c = 0, r = 0; i < m; i++) { // r 是最右回文边界, c 是对应回文中心.
    R[i] = r < i ? 1 : min(R[c * 2 - i], r - i + 1); // 若 i <= r, 则根据对称性继承信息.
    while(t[i - R[i]] == t[i + R[i]]) R[i]++;
    ans = max(ans, R[i] - 1);
    if(i + R[i] - 1 > r) c = i, r = i + R[i] - 1; // 更新 r 和 c.
  }
  cout << ans << endl;
  return 0;
}

1.4 结论与应用

Manacher 本身证明了一个关于回文子串的结论：一个字符串的本质不同回文子串个数不大于 n。因为所有以 i 为回文中心的长度小于等于 \min(r - i + 1, R_{2c - i}) 的回文子串均与以 2c - i 为回文中心的对应长度的回文子串相等。故以 i 为回文中心，每找到一个在此之前没有出现过的回文子串，均会使 r 增加 2（找到回文子串后，因为分隔符回文再扩展一步）。注意，使 r 增加并不一定代表找到新的回文子串。

当然，我们也可以不借助 Manacher 直接证明这一结论。考虑在每个回文子串第一次出现处计入贡献。若存在两个本质不同回文子串 p, q 在同一右端点处贡献答案，不妨设 |p| < |q|，则根据回文性 q[1, |p|] = p，与 p 第一次出现在 q[|q| - |p| + 1, |q|] 处矛盾。因此一个右端点至多贡献一个本质不同回文子串。

利用 Manacher，我们可以求出以每个字符开头或结尾的最长回文子串：考虑位置 i 及其最长回文半径 R_i，若 i + R_i - 1 > r，根据算法，用 i + R_i - 1 更新 r。更新前枚举 j\in[r + 1, i + R_i - 1]，若 t_j 对应原串字符 s_k 而非分隔符，则原串中以 s_k 结尾的最长回文子串长度为 j - i + 1。通过分奇偶性讨论和模拟可证其正确性。代码实现见例题 P4555。

1.5 例题

UVA11475 Extend to Palindrome

找到最小的使得 s[l, r] 为回文串的 l，则答案即 s 加上 s[1, l - 1] 翻转后的结果。代码。

P3501 [POI2010] ANT-Antisymmetry

借鉴 Manacher 的思路，我们对每个位置求出最长 Anti-symmetry 半径。同样的，记录最右边的回文区间，快速继承和扩展做到均摊线性。代码。

P4555 [国家集训队] 最长双回文串

对每个位置求出以该字符结尾和开头的最长回文子串 lft_i 和 rt_i，则 \max_{i = 1} ^ {n - 1} lft_i + rt_{i + 1} 即为所求。

时间复杂度线性。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, ans, R[N], lft[N], rt[N];
char s[N], t[N];
int main() {
  scanf("%s", s + 1), n = strlen(s + 1);
  t[0] = '!', t[m = 1] = '@';
  for(int i = 1; i <= n; i++) t[++m] = s[i], t[++m] = '@';
  t[++m] = '#';
  for(int i = 1, c = 0, r = 0; i < m; i++) {
    R[i] = i > r ? 1 : min(R[2 * c - i], r - i + 1);
    while(t[i - R[i]] == t[i + R[i]]) R[i]++;
    if(i + R[i] - 1 > r) {
      for(int j = r + 1; j < i + R[i]; j++) if(j & 1 ^ 1) lft[j >> 1] = j - i + 1; // 新串的偶数位置对应一个原串字符.
      c = i, r = i + R[i] - 1;
    }
  }
  for(int i = m - 1, c = m, r = m; i; i--) { // 倒过来做一遍 Manacher.
    R[i] = i < r ? 1 : min(R[2 * c - i], i - r + 1);
    while(t[i - R[i]] == t[i + R[i]]) R[i]++;
    if(i - R[i] + 1 < r) {
      for(int j = i - R[i] + 1; j < r; j++) if(j & 1 ^ 1) rt[j >> 1] = i - j + 1;
      c = i, r = i - R[i] + 1;
    }
  }
  for(int i = 1; i < n; i++) ans = max(ans, lft[i] + rt[i + 1]);
  cout << ans << endl;
  return 0;
}

P1659 [国家集训队] 拉拉队排练

因为题目要求奇回文串，所以只考虑以下标 i 为回文中心。若新串位置 k 对应原串下标 i，则此时所有长度 j \in [1, \frac{R_k} 2] 的回文半径均存在，相当于对 1, 3, \cdots, R_k - 1 进行单点加，最后全局查询。差分维护即可。

时间复杂度是快速幂的 \mathcal{O}(n\log n)。代码。

P5446 [THUPC2018] 绿绿和串串

如果 pre_i 能生成 s，则以 i 为回文中心时，要么存在顶到结尾的回文串，要么存在顶到开头的回文串且 pre_{2i - 1} 能生成 s。

Manacher 求出每个位置的最长回文半径后倒过来 dp 一遍即可。

时间复杂度 \mathcal{O}(n)。代码。

2. Z 算法 / 扩展 KMP

扩展 KMP 在 NOI 大纲里是 9 级算法。它和 KMP 没有关系。

2.1 算法简介

定义字符串 s 的 Z 函数 z_i 表示 s 的 i 后缀与 s 本身的最长公共前缀长度，即 z_i = |\mathrm{lcp}(suf_i, s)|。z_1 无用，一般令 z_1 = n。

每次暴力匹配，时间复杂度 \mathcal{O}(n ^ 2)。它没有利用任何已经求出的 z_1, z_2, \cdots, z_{i - 1} 的信息，很不优美。

Z 算法利用已经求得的信息的性质，通过增量法求出 Z 函数。

称 [i, i + z_i - 1] 为 i 的匹配段，也称 Z-box。据定义，s[i, i + z_i - 1] = s[1, z_i]。

类似 Manacher，实时维护最靠右侧的匹配段 [l, r]。匹配到位置 i 时，分两种情况讨论：

• 若 i > r，直接暴力匹配。
• 若 i \leq r，因为 s[1, r - l + 1] =s [l, r]，所以 s[i, r] = s[i - l + 1, r - l + 1]。因此 suf_i 的 r - i + 1 前缀和 suf_{i - l + 1} 的 r - i + 1 前缀相等。故首先令 z_i \gets \min(r - i + 1, z_{i - l + 1})，然后暴力匹配。

读者可以发现 Z 算法和 Manacher 的核心思想几乎一模一样。

时间复杂度：当 z_{i - l + 1} < r - i + 1 时，z_i 不可能继续向下匹配，否则与 z_{i - l + 1} 的最大性矛盾。因此，每次成功的匹配都会使 r 增加 1。时间复杂度是优秀的线性。

2.2 应用

Z 函数可以用于做特定类型的字符串匹配：求字符串 t 的每个后缀 i 与 s 的最长公共前缀长度 p_i。

• 解法 1：令 s' = s + c + t，其中 c 是任意不属于 s, t 字符集的分隔符。对 s' 求 Z 函数。
• 解法 2：先求出 s 的 Z 函数。然后类似求 Z 函数的方法，维护最右匹配段 [l, r] 表示 t[l, r] = s[1, r - l + 1]，若 i > r 则暴力匹配，否则令 p_i = \min(z_{i - l + 1}, r - i + 1)。

两种解法本质相同，因为 Z 算法本身相当于用 s 匹配自己，类似 KMP 用自己匹配自己的方式求出 nxt 数组。

2.3 例题

P5410 【模板】扩展 KMP（Z 函数）

#include <bits/stdc++.h>
using namespace std;
const int N = 2e7 + 5;
char s[N], t[N];
int n, m, z[N], p[N];
int main() {
  scanf("%s%s", t + 1, s + 1);
  m = strlen(t + 1), n = strlen(s + 1);
  z[1] = n;
  for(int i = 2, l = 0, r = 0; i <= n; i++) {
    z[i] = i > r ? 0 : min(z[i - l + 1], r - i + 1);
    while(s[1 + z[i]] == s[i + z[i]]) z[i]++; // 因为 i 不等于 1, 所以 i + z[i] 超出下标时空字符和 s[1 + z[i]] 必然不等, 判断句不成立.
    if(i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  for(int i = 1, l = 0, r = 0; i <= m; i++) {
    p[i] = i > r ? 0 : min(z[i - l + 1], r - i + 1);
    while(p[i] < n && s[1 + p[i]] == t[i + p[i]]) p[i]++; // 应判断 p[i] 小于模式串长度而非匹配串长度.
    if(i + p[i] - 1 > r) l = i, r = i + p[i] - 1;
  }
  long long ans = 0;
  for(int i = 1; i <= n; i++) ans ^= 1ll * i * (z[i] + 1);
  cout << ans << endl;
  ans = 0;
  for(int i = 1; i <= m; i++) ans ^= 1ll * i * (p[i] + 1);
  cout << ans << endl;
  return 0;
}

CF432D Prefixes and Suffixes

KMP 找到完美子串，Z 算法 + 差分求出现次数。

时间复杂度线性。代码。

CF526D Om Nom and Necklace

重新表述题意：若 S 能被表示成 AAA\cdots AB，其中 A 出现了 k 次且 B 是 A 的前缀，则 S 符合要求。

枚举所有 k \mid i。根据 border 的性质，若 S 有长为 |S| - p 的 border，则 S 有周期 p。因此 KMP 求出 S 的 nxt 数组。若 i - nxt_i \left | \frac i k \right. 说明 S[1, i] 由 k 个相同字符串拼接而成，即 |A| = \frac i k。

此时考虑可能的 B 的最长长度 r，即 \min(|A|, |\mathrm{lcp}(S[i + 1, |S|], S)|)，后者用 Z 算法求。这说明 S[1, i\sim i + r] 均可成为答案，差分维护即可。

时间复杂度线性。代码。

3. 后缀数组

前置知识：计数排序，基数排序，倍增。

后缀数组（Suffix Array, SA）的思想与实现非常简单，基础的倍增思想加上排序，但其扩展得到的 ht 数组功能强大且适用性广，使得它在 OI 界有广泛应用。

后缀数组在 NOI 大纲里是 8 级算法。

3.1 相关定义

• 定义 rk_i 表示 suf_i 在所有后缀中的字典序排名。由于任意后缀长度不同，故不存在两个后缀排名相同。例如 \texttt {aabab}，有 \texttt{aabab} < \texttt{ab} < \texttt{abab} < \texttt{b} < \texttt{bab}，所以 rk = \{1, 3, 5, 2, 4\}。
• 定义 sa_i 表示排名为 i 的后缀的开始位置。它与 rk 互逆：rk(sa_i) = i，这个 i 表示排名；sa(rk_i) = i，这个 i 表示位置。这就是 后缀数组。

结论 1 非常容易理解，因为字典序距离越近，LCP 越长。例如，按字典序排序后，两个 \tt abcd 开头的字符串之间不会出现以 \tt abcc 或 \tt abce 开头的字符串。

若希望求出 ht 数组，自然考察其性质。

假设 ht_i 已知，则 |\mathrm{lcp}(sa_i, sa_{i - 1})| = ht_i。考察 suf(sa_{i - 1} + 1) 和 suf(sa_i + 1)，即排名分别为 i - 1 和 i 的后缀位置加上 1 后对应的后缀。当 ht_i > 0 时，显然有 |\mathrm{lcp}(sa_{i - 1} + 1, sa_i + 1)| = ht_i - 1，且根据 rk(sa_{i - 1}) < rk(sa_i) 容易证明 rk(sa_{i - 1} + 1) < rk(sa_i + 1)。

令 p 和 q 分别表示排名为 i 和 i - 1 的后缀位置加 1，即 sa_i + 1 和 sa_{i - 1} + 1，我们尝试求出 rk_p 对应的 ht。先梳理一下已有的信息：

它们合起来表达了：存在位置 q，满足其排名小于 p 的排名，且它们对应后缀的 LCP 长度为 ht_i - 1。

相信部分读者此时已经想到一些了不起的性质了。

排名为 rk_p - 1 的后缀 suf_r 的排名要么等于 rk_q，此时 q = r，要么夹在 rk_q 和 rk_p 之间，因为 rk_r 是小于 rk_p 的最大正整数 rk_p - 1，而 rk_q 小于 rk_p。因此，根据结论 1，其与 p 之间的 LCP 长度必然不小于 ht_i - 1，即 ht(rk_p) \geq ht_i - 1。

进一步地，注意到 rk_p 表示排名为 i 的后缀位置加 1 的排名，i 表示排名为 i 的后缀位置的排名，即 ht(rk(sa_i + 1)) \geq ht(rk(sa_i)) - 1。换元，令 u = sa_i + 1，我们得到了 ht 数组的核心性质（u > 1）：

• 没有讨论 ht_i = 0 的情况，不过因为 ht 非负所以同样满足上式。
• 因为 s_0 为空字符，所以求出的 ht(1) = 0。

如上图，p = sa_i + 1，q = sa_{i - 1} + 1，ht_i - 1 = |\mathrm{lcp}(p, q)| \leq |\mathrm{lcp}(p, r)| = ht(rk_p)。

根据该性质，我们可以按 i 递增的顺序递推求解 ht(rk_i)。实际上就是按 i 从小到大的顺序计算位置为 i 的后缀与排名为其排名减 1 的后缀的 \mathrm{lcp}。想象一个指针从 s_1 扫到 s_n，指针右移时，将右移前排名减 1 的后缀对应位置也向右移动一位，就可以理解 ht 数组的性质了。

下方代码中，k 指针向右移动的总次数为线性，因为每次 i 增加只会使得 k 减少 1，而 k \leq n。

for(int i = 1, k = 0; i <= n; i++) {
  if(k) k--;
  while(s[i + k] == s[sa[rk[i] - 1] + k]) k++; // sa[rk[i]] = i, 需要保证 s[0] 和 s[n + 1] 为空字符 (多测清空), 否则可能出错.
  ht[rk[i]] = k;
}

3.4 应用

3.4.1 任意两个后缀的 LCP

有了 ht 数组，我们可以快速求一个字符串 s 的 i 后缀与 j 后缀的最长公共前缀 \mathrm{lcp}(i, j)。

结论 2：设 rk_i < rk_j，则 |\mathrm{lcp}(i, j)| = \min_{p = rk_i + 1} ^ {rk_j} ht_p。

证明：设 t = |\mathrm{lcp}(i, j)|。

根据字典序的定义，所有排名在 rk_i 和 rk_j 之间的后缀 suf_k(rk_i \leq rk_k \leq rk_j) 的前 t 个字符均与 suf_i 和 suf_j 相等。又因为 suf_i[t + 1] \neq suf_j[t + 1]，所以存在两个相邻的排名 p, p + 1，使得 suf(sa_p)[t + 1] \neq suf(sa_{p + 1})[t + 1]。这样，对于所有 p \in [rk_i + 1, rk_j]，ht_p \geq t，且存在 ht_p = t。\square

简单地说，i 后缀与 j 后缀的最长公共前缀长度就是夹在这两个后缀排名之间的 ht 数组的最小值。可以感性理解为字典序相差越大，前缀差别越大。

上图为对 \tt aabaaaab 后缀排序的结果及其 ht 数组，由矩形框起来的两个字符串相等。形象地，两个后缀之间的 \mathrm{lcp} 就是它们排名之间所有矩形宽度的最小值，即 ht 的最小值。

如果将整张图逆时针旋转 90 度，将得到一张矩形柱状图。ht 恰好表示了每个矩形的高度，这可能也是 height 这一名称的来源。正因如此，SA 可以和单调栈相结合：众所周知，单调栈可以求出柱状图中面积最大的矩形。

查询区间最值，使用 ST 表维护即可做到 \mathcal{O}(n\log n) 预处理，\mathcal{O}(1) 在线回答询问。

注意点：

• 查询范围是 rk_i, rk_j 而非 i, j。
• 当 rk_i > rk_j 时，需要 swap(i, j)。
• 左边界要加 1。
• 需特判 i = j 的情况。

3.4.2 本质不同子串数

可以用 s 的所有后缀的所有前缀表示其所有子串。考虑每次添加一个后缀，并删去这个后缀与已经添加的后缀的所有重复前缀，即 \max_{j\in S} |\mathrm{lcp}(s_i, s_j)|。

因为 \max_{j < i}|\mathrm{lcp}(sa_i, sa_j)| = |\mathrm{lcp}(sa_i, sa_{i - 1})| = ht_i，所以按照 sa_1, sa_2, \cdots, sa_n 的顺序添加后缀，sa_i 对答案的贡献即 (n - sa_i + 1) - ht_i。化简得

上述做法求出了 s 的所有后缀的本质不同前缀数量。我们可以将其扩展到求 s 的某个后缀集合 S 的所有本质不同前缀数量。设 S 的所有元素（位置）按排名从小到大排序后分别为 p_1, p_2, \cdots, p_{|S|}，类似地，答案为

后者对 ht 预处理 ST 表后 \mathcal{O}(|S|) 求出。

3.4.3 结合单调栈