当前位置：首页 > news >正文

字符串（Updating）

news 2026/7/24 8:17:53

SA

后缀数组。下面可以用 $i$ 表示 $s[i\dots n]$。

要记两个东西：$sa_i, rk_i, sa_i$ 表示后缀排序后第 $i$ 小的是哪个后缀，$rk_i$ 表示第 $i$ 个后缀是第几小的。显然 $sa[rk[i]]=rk[sa[i]]=i$。

首先考虑 $\mathcal{O}(n \log^2 n)$ 做法，我们记所有长度为 $w$ 的子串排序后，第 $i$ 个子串，是 $sa_w[i]$，$s[i\dots i + w - 1]$ 的排名为 $rk_w[i]$，默认 $s$ 超过 $n$ 的部分是空字符。我们让 $w$ 从 $1$ 开始，以 $rk_w[i]$ 为第一关键字，$rk_w[i+w]$ 为第二关键字排序，这样就可以得到 $sa_{2w}$ 和 $rk_{2w}$，当 $w \ge n$ 时就得到了所有后缀的 $sa$ 和 $rk$。这被称为倍增法。

然后考虑优化，发现两个关键字都很小，直接基数排序，先对第二关键字计数排序，再对第一关键字计数排序，时间复杂度 $\mathcal{O}(n \log n)$，但是常数还是较大，有如下优化：

排第二关键字的时候不用计数排序，只要将所有 $i + w > n$ 的 $i$ 放在最前面，剩下的位置考虑从小到大枚举 $i$，若 $sa_w[i] > w$ 则 $rk_w[sa_w[i]]$ 可以作为 $sa_w[i] - w$ 的第二关键字，于是按顺序加入这样的 $sa_w[i]-w$。
若一次排序后所有 $rk$ 已经不同，就已经求出了最后的 $sa$，直接结束即可。
每次计数排序的值域可以缩小至上次排序后的 $rk$ 的最大值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = 1e6 + 10;
template<typename T> void dbg(const T &x) { cout << x << '\n'; }
template<typename Type, typename ...Types> void dbg(const Type &arg, const Types &...args) { cout << arg << ' '; dbg(args...); }
namespace Loop1st {
int n, m, sa[N], id[N], rk[N << 1], oldrk[N << 1], cnt[N];
char s[N];
void main() {cin >> (s + 1);n = strlen(s + 1);for (int i = 1; i <= n; i++) cnt[rk[i] = s[i]]++;m = 127;for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];for (int i = n; i; i--) sa[cnt[rk[i]]--] = i;int p = 0;for (int w = 1; w < n; w <<= 1, m = p) {int cur = 0;for (int i = n - w + 1; i <= n; i++) id[++cur] = i;for (int i = 1; i <= n; i++) if (sa[i] > w) id[++cur] = sa[i] - w;memset(cnt, 0, (m + 1) << 2);for (int i = 1; i <= n; i++) cnt[rk[id[i]]]++;for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];for (int i = n; i; i--) sa[cnt[rk[id[i]]]--] = id[i];p = 0;memcpy(oldrk, rk, (n + 1) << 2);for (int 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;} if (p == n) break;}for (int i = 1; i <= n; i++) cout << sa[i] << " \n"[i == n];
}}int main() {// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);ios::sync_with_stdio(false); cin.tie(0);clock_t Start = clock();int Test = 1;// cin >> Test;for (int tc = 1; tc <= Test; tc++) Loop1st::main();clock_t End = clock();cerr << "Time = "; cerr << fixed << setprecision(6) << 1. * (End - Start) / CLOCKS_PER_SEC << '\n';return 0;
}

另外，SA 还可以用于求 height 数组，定义 $height[i]=\text{LCP}(sa[i], sa[i - 1]), height[1] = 0$，即两个相邻后缀的 $\text{LCP}$。我们有引理：

\[height[rk[i]] \ge height[rk[i - 1]] - 1 \]

证明：$RHS \le 0$ 时显然成立，当 $height[rk[i - 1]] > 1$ 时，$\text{LCP}(sa[rk[i - 1]], sa[rk[i - 1] - 1]) > 1$，即 $\text{LCP}(i - 1, sa[rk[i-1]-1]) > 1$，我们设这两个后缀的 $\text{LCP}$ 为 $aA$，其中 $a$ 是一个字符，$A$ 是一个字符串，那么 $i - 1$ 可以表示为 $aAD$，$sa[rk[i-1]-1]$ 可以表示为 $aAB$，根据 $sa$ 的性质有 $B < D$。而 $i$ 可以表示为 $AD$，而 $sa[rk[i]-1]$ 的 $rk$ 只比 $i$ 小 $1$，且 $AB < AD$，即 $AB$ 的 $rk$ 比 $i$ 至少小 $1$，于是有 $AB \le sa[rk[i]-1] < AD$，所以 $$height[i]=\text{LCP}(i, sa[rk[i]-1]) \ge |A|=height[rk[i-1]]-1$$

\[height[i] \ge height[rk[i-1]]-1 \]

于是可以 $\mathcal{O}(n)$ 计算。

	for (int i = 1, k = 0; i <= n; i++) {if (k) k--;while (s[i + k] == s[sa[rk[i] - 1] + k]) k++;height[rk[i]] = k;}

应用

[JSOI2007] 字符加密

将 $S$ 复制一遍变为 $SS$ 之后后缀排序即可。

[USACO07DEC] Best Cow Line G

每次相当于比 $L$ 开头的后缀和 $R$ 结尾的前缀，重复不用管因为不重复部分如果比不出来，那随便取哪个，所以将反串接到结尾，中间加个特殊字符跑 SA，然后判断 $rk$ 即可。

【模版】AC 自动机

子串一定是前缀的后缀，在 $sa$ 数组上二分并比较即可，比 ACAM 多一个 $\log |T|$ 的复杂度。

求两子串 LCP

LCP Lemma:
对于 $i < j < k \le n$，我们有 $\text{LCP}(i, k) = \min(\text{LCP}(i, j), \text{LCP}(j, k))$。证明显然，详情可见许智磊--后缀数组。
LCP Theorem:
$\text{LCP}(sa[i], sa[j]) = \min\limits_{k=i+1}^j height[k]$。证明由 LCP Lemma 直接得出。
于是可以变为 RMQ。

比较两子串大小关系

对于两子串 $A = s[a\dots b], B = s[c\dots d]$，若 $\text{LCP}(a, c) \ge \min(|A|, |B|)$ 则 $A < B \Leftrightarrow |A| < |B|$。否则，$A < B \Leftrightarrow rk[a] < rk[c]$。

本质不同子串数目

即后缀的前缀数量减去重复。

考虑按后缀排序的顺序枚举后缀 $sa[i]$，那么每次新增的子串要除去与上一个串的 $\text{LCP}$ 即 $height[i]$。这个后缀剩下的前缀一定是新增的，如果剩下的前缀中有一个在 $sa[j]$ 中出现过，那么 $\text{LCP}(sa[i], sa[j]) > height[i]$，然而 $\text{LCP}(sa[i], sa[j]) = \min(height[k]) \le height[i]$，矛盾。

所以最终答案就是 $\dfrac{n(n+1)}{2}-\sum\limits_{i=1}^n height[i]$。