CSP-S 2025 第三题 后缀数组解法

作者: tiankonguse | 更新日期:

后缀数组的构造是关键，分组、分隔符、上下界等都需要权衡。

本文首发于公众号：天空的代码世界，微信号：tiankonguse

零、背景

目前我已经做了历年 CSP-J/S 的所有常规算法题目。
CSP-J 题解：2025、2024、2023、2022、2021、2020、2019。
CSP-S 题解：2025、2024、2023、2022、2021、2020。

还写了题型分析：《CSP-J 题型分析》和《CSP-S 题型分析》。

备考相关：策略与技巧：得分技巧、环境准备。
常见算法整理：二分、线段树、状态最短路、动态规划、数学、常见算法和数据结构。

完整版题解（含代码/数据）：CSP-J：2025；CSP-S：2025。

在之前的《CSP-S 2025 第二轮比赛题解》文章中，第三题“谐音替换”（replace）我介绍了 AC 自动机 + 哈希的解法。
后来在《CSP-S 2025 第三题字典树 Trie 解法》 介绍了 Trie 解法。

今天来介绍下后缀数组解法，并分析其优缺点。

PS：源码放在网盘，公众号回复 CSP-2025 获取。

一、简单认识后缀数组

后缀数组是解决字符串匹配问题的强大工具。
我们可以直接套用后缀数组的模版来解决这个问题。

后缀数组，顾名思义，是一个字符串的所有后缀的数组。

不过这个数组预处理后，是按字典序排序的。
比如字符串 banana 的后缀数组为：

5: a
3: ana
1: anana
0: banana
4: na
2: nana

排序后，自然就需要知道一个后缀的排序是多少，称为排名 rank（下标从0开始）。
例如上面的后缀数组中，位置 1 的后缀是 anana，排名是 2，记为 rank[1] = 2。

与此相反的，我们也可以通过排名来找到对应的后缀，称为 sa 数组（下标从0开始）。
例如上面的后缀数组中，排名第 2 的是位置 1 的后缀 anana，记为 sa[2] = 1。

另外，后缀数组中还有一个重要的概念是 height 数组。
height 数组表示相邻后缀的最长公共前缀长度。

例如上面的后缀数组中，排名第 1 的后缀 ana 和排名第 2 的后缀 anana 的最长公共前缀是 ana，长度为 3，记为 height[2] = 3。

有了 height 数组，就可以预处理出一个 ST 表，从而可以 O(1) 计算出任意两个后缀的最长公共前缀长度 lcp。

好的，基础概念介绍完了，涉及四个概念。

  • 后缀数组 sa：排名找后缀位置
  • 排名 rank： 后缀位置找排名
  • height 数组：和上一个的 LCP 长度
  • lcp：任意两个后缀的 LCP 长度

另外，后缀数组的算法实现有很多种。

暴力字符串排序，复杂度是 O(n^2logn)。
倍增思想，复杂度是 O(nlogn)。
DC3 算法，复杂度是 O(n)。

二、题目回顾

题目：给 n 个字符串二元组 (s1, s2)，以及 q 个询问二元组 (t1, t2)。
问对于每个 (t1, t2)，有多少个 (s1, s2) 满足在 s1 中的子串 t1 替换为 t2 后可以得到字符串 s2 。

经过一番分析，可以发现这些字符串需要按键进行分组处理。
s1 可以分为三部分：公共前缀 A、替换部分 B、公共后缀 C。
s2 也可以分为三部分：公共前缀 A、替换部分 D、公共后缀 C。
(t1, t2) 也是类似的，t1 分为 AA、B、CC，t2 分为 AA、D、CC。

要想满足替换条件，第一个条件是必须满足 (s1, s2) 的 B->D 和 (t1, t2) 的 B->D 是相同的。
所以，可以根据 B->D 来对数据进行分组。

分组后， (s1, s2) 转化为了 (A, C)。
(t1, t2) 也转化为了 (AA, CC)。

此时，要满足替换条件，A 必须是 AA 的后缀，C 必须是 CC 的前缀。

所以，问题转化为了： 对于每个询问 (AA, CC)，统计有多少个 (A, C) 满足 A 是 AA 的后缀，C 是 CC 的前缀。

AC 自动机的解法中已经介绍了，通过二元组拼接为字符串，可以把转化为子串匹配问题。

简单来说，把 (A, C) 拼接为 A#C，把 (AA, CC) 拼接为 AA#CC。
问题就转化为了 ： 统计有多少个 A#C 是 AA#CC 的子串。

三、朴素构造

这里有三种构造方式，我们分别来看下。

方式1：所有询问直接拼接法

第一步：构造后缀字符串

由于不同的B->D 会有相同的 (A, C) 和 (AA, CC)，所以 B 和 D 也需要带上。
比如拼接为 A#B#D#C，然后再使用另外一个字符 $连起来。

另外，后缀数组要求最后也要一个独一无二的结束符，所以我们在最后再加一个 *。
大概如下：

A1#B1#D1#C1$...An#Bn#Dn#Cn$AA1#BB1$DD1#CC1$...AAq#BBq#DDq#CCq$*

以样例数据为例。

4 2
xabcx xadex
ab cd
bc de
aa bb
xabcx xadex
aaaa bbbb

构造出后缀数组后，主要看排名影响答案的部分连续排名。

#bc#cd#$...   匹配串 bc->de
#bc#de#ex$... 查询串 xabcx->xadex
#bc#de#ex$... 匹配串 xabcx->xadex

可以发现，由于匹配后再之后的字符的随机的，如果遇到完全匹配时，查询串可能在匹配串前面，也可能在后面。

第二步：枚举匹配串，查找区间

构造字符串时，还需要记录每个匹配串的起始位置。
这样，就可以通过位置找到对应的排名 rank[offset]。

for (int i = 0; i < n; i++) {
  patterns[i].offset = bufLen;
  buf.append(patterns[i].s);
  buf.push_back('#');
}

有了匹配串的排名后，接下来就需要找这个匹配串是哪些查询串的子串。
对每个匹配串分别向前二分和向后二分查找，找到 LCP 大于等于匹配的长度的上下边界[l,r]。

auto FindR2 = [&](const int r1, const int len) -> int {
  int l = r1, r = totalLen;
  while (l < r) {
    int mid = (l + r) / 2;
    int lcp = SA::LcpRK(r1, mid);
    if (lcp >= len) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }
  return r - 1;
};

找到了区间后，代表这个匹配串是区间内后缀的子串。
接着使用差分数组、树状数组、线段树等数据结构进行区间排名加一。

for (auto& pattern : patterns) {
  int pr = SA::rk[pattern.offset1];
  int r1 = FindR1(pr, pattern.s.length());
  int r2 = FindR2(pr, pattern.s.length());
  assert(r1 <= r2);
  differenceArray[r1]++;
  differenceArray[r2 + 1]--;
}

对于一个查询串，后缀串有很多，每个都可能匹配到若干子串，答案是这些子串的和。

前面已经计算出每个后缀排名匹配的子串个数了。
现在需要枚举所有排名，判断这些排名对应的后缀是哪个查询串的，然后把这个后缀的答案加到对应查询串的答案中。

怎么由排名找到查询串呢？
排名可以找到后缀位置 sa[rank]。
每个查询串有起始位置和结束位置，可以通过二分找到这个后缀位置在哪个查询串内。

auto FindIdx = [&](int offset) {  //
  int i = upper_bound(queryOffset, queryOffset + qn, offset) - queryOffset;
  if (i == 0) return -1;
  i--;
  auto& query = queries[i];
  if (offset >= query.offsetLeft && offset < query.offsetRight) {
    return query.idx;
  }
  return -1;
};

由于这里需要遍历排名，所以可以同时计算下差分数组的前缀和。

int preSum = 0;
for (int rank = 0; rank < totalLen; rank++) {
  preSum += differenceArray[rank];
  if (preSum == 0) continue;  // 剪枝
  int offset = SA::sa[rank];
  int queryIdx = FindIdx(offset);
  if (queryIdx == -1) continue;  // 非查询
  ans[queryIdx] += preSum;
}

四、构造上界

在朴素构造中，查询串和匹配串是混合在一起的。
所以在遇到完全匹配时，查询串可能在匹配串前面，也可能在后面。

如果匹配串后面追加的特殊字符比查询串小一些，这样就可以保证查询串一定在匹配串的后面。

例如下面的示例，匹配串追加 1，查询串追加 2，排名如下。

#bc#cd#1...   匹配串 bc->de
#bc#de#ex1... 匹配串 xabcx->xadex
#bc#de#ex2... 查询串 xabcx->xadex

这时候，查询串一定在匹配串的后面。
查询串的排名就是上界，只需要二分找到下界即可。

另外，由于自己是上界，自己肯定不是答案，也可以直接排除掉，后续根据前缀和计算答案时，计算量也会少一些。

for (auto& pattern : patterns) {
  int r1 = SA::rk[pattern.offset1];
  int r2 = FindR2(r1, pattern.s.length());
  assert(r1 <= r2);
  r1++;  // 自己排除掉
  if (r1 <= r2) {
    differenceArray[r1]++;
    differenceArray[r2 + 1]--;
  }
}

五、构造下界

基于构造上界的思路，我们也可以复制一遍匹配串，构造出一个下界来。

大于小写字母 ‘z’ 的字符有 { | } ~ 四个。
所以可以选择其中一个，来当做下界的特殊字符。

// S(最小): S3 + '('  // 40
// T(大于S): T3 + '?' // 63
// S(大于T): S3 + '}' // 125
// 结尾: '$' // 36
for (int i = 0; i < n; i++) {
  patterns[i].offset1 = buf.size(); // 上届起始位置
  buf.append(patterns[i].s);
  buf.push_back('(');
  patterns[i].offset2 = buf.size(); // 下届起始位置
  buf.append(patterns[i].s);
  buf.push_back('}');
}
for (int i = 0; i < q; i++) {
  queries[i].offsetLeft = buf.size(); // 查询串起始位置
  buf.append(queries[i].t);
  buf.push_back('?');
  queries[i].offsetRight = buf.size(); // 查询串结束位置
}
buf.push_back('$');

这样，就不需要二分查找，直接得到一个下界和上界。

for (int i = 0; i < n; i++) {
  int r1 = SA::rk[patterns[i].offset1];
  int r2 = SA::rk[patterns[i].offset2];
  assert(r1 < r2);
  differenceArray[r1]++;
  differenceArray[r2 + 1]--;
}

当然，这样做也有代价，匹配串的长度翻倍了，内存直接会爆掉。

在不构造下界的情况下，使用 O(n log n) 的倍增法通常能得到约 40 分的效果。

如果把模板换成线性时间的 DC3（Skew）算法，构造时间理论上可降为 O(n)，可以得 50 分。

但 DC3 需要额外的临时数组，常常造成峰值内存显著增大。
在我的测试里，直接启用 DC3 实现会因为内存占用过高而出现运行时错误（内存不足）。
因此在内存受限的环境下，建议先按 B->D 分组再在每组内部构造后缀数组；这是在时间与内存之间的一个实用折中。

50分

六、分组优化

直接对所有查询构造后缀数组显然不合理。
因为不同的 B->D 不可能匹配上，另外 B->D 也有大量的重复，都会浪费空间。

所以需要根据 B->D 进行分组处理，只存 A#C 和 AA#CC。
对每个分组单独构造后缀数组，计算答案。

使用 O(n log(n)) 的算法，可以得 70 分。
如果在分组后对每组采用线性时间的 DC3（Skew）算法，通常可以把构造时间降到接近 O(n)，从而得到得到 100 分。

50分

七、总结

后缀数组的构造方式有很多种，不同的构造方式直接决定了时间复杂度、空间复杂度、代码复杂度。

例如不分组，空间直接爆炸了。
匹配串与查询串后缀不做区分，就要写两个二分查找查找边界。
而同时构造上下界，节省一个二分查找，空间却翻倍了。

这些都是需要根据题目数据范围进行权衡的。

总体来看，后缀数组还是比较难的。
CSP-J/S 一般不要求掌握后缀数组，打算冲刺 NOIP 的同学可以了解一下。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code

本文首发于公众号：天空的代码世界，微信号：tiankonguse
如果你想留言，可以在微信里面关注公众号进行留言。

关注公众号,接收最新消息

置顶文章

tiankonguse + ≡
穿越