CSP-S 2025 第三题 AC自动机复杂度分析与优化

作者: tiankonguse | 更新日期:

本文详细分析AC自动机在CSP-S 2025第三题中的应用，解释其复杂度从O(n*q)优化到O(L)的过程，并说明为何在实际中不会超时。

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

零、背景

在《CSP-S 2025 第二轮比赛题解》中，第三题”谐音替换”（replace）我介绍了AC自动机+哈希的解法。

随后在《CSP-S 2025 第三题字典树Trie解法》介绍了 Trie 解法；在《CSP-S 2025 第三题后缀数组解法》介绍了后缀数组解法。

官方数据发布后，我发布了《CSP-S 2025 完整版题解（含源码与测试数据）》。
文中提到AC自动机的匹配过程：虽然 fail 指针加速了匹配，但在最坏情况下如果每次都沿 fail 链匹配，复杂度可能达到O(n*q)。

HY-Y 同学与我探讨了复杂度是否为O(n*q)，我给出了严格证明，最坏复杂度确实是O(n*q)。

qwqss 同学反馈，对 fail 树进行预处理后，复杂度可以严格优化到O(L)。

本文详细介绍为何最坏复杂度是O(n*q)，为何在实际中不会超时，以及如何优化到O(L)。

PS：源码已上传网盘，公众号回复 CSP-2025 获取。

50分

一、题目回顾

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

经过一番分析，可以发现这些字符串需要按替换映射键 B->D 进行分组处理。
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 的子串。

这是典型的多模式匹配问题，AC 自动机可以直接查询。

字典树构造代码如下：

void insert(const int root, char s[]) {
  int u = root;
  for (int i = 0; s[i]; i++) {
    int& son = tr[u].son[Hash(s[i])];  // 下一个子结点的引用
    if (!son) son = NextNode();        // 如果没有则插入新结点，并初始化
    u = son;                           // 从下一个结点继续
  }
  tr[u].cnt++;
}

fail 指针构造如下：

void build(const int root) {
  queue<int> q;
  // 为每个独立的 root 设置自己的 fail/缺失转移指向自己
  tr[root].fail = root;
  // 根节点的直接子结点：设置其 fail 为 root，并入队；根节点缺失转移指向 root 自身
  for (int i = 0; i < kKind; i++) {
    if (tr[root].son[i]) {
      tr[tr[root].son[i]].fail = root;
      q.push(tr[root].son[i]);
    } else {
      tr[root].son[i] = root;  // 根节点缺失转移指向 root 自身
    }
  }
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < kKind; i++) {
      if (tr[u].son[i]) {                               // 存在对应子结点
        tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];  // 只用跳一次 fail 指针
        q.push(tr[u].son[i]);                           // 并加入队列
      } else {
        tr[u].son[i] = tr[tr[u].fail].son[i];  // 将不存在的字典树的状态链接到了失配指针的对应状态
      }
    }
  }
}

最后是 AC 自动机查询。
可以看到，每个节点都会顺着失败指针往上遍历。

ll query(const int root, char t[]) {
  int u = root;
  ll res = 0;
  for (int i = 0; t[i]; i++) {
    u = tr[u].son[Hash(t[i])];  // 转移
    // 沿 fail 链累加，终止条件为回到当前 automaton 的 root
    for (int j = u; j != root; j = tr[j].fail) {
      res += tr[j].cnt;
    }
    // 如果 root 本身也为模式结尾（极少见），也需要计入
    if (tr[root].cnt) res += tr[root].cnt;
  }
  return res;
}

q 个询问，需要逐个查询 AC 自动机。

// q 个询问
while (q--) {
  int root = ACIndex[h];
  ll res = AC::query(root, s3);
  printf("%lld\n", res);
}

三、AC自动机复杂度分析

q 个询问的复杂度取决于每次查询的代价。
每次查询 AC 自动机时，都会顺着 fail 链找到所有匹配的子串。
如果 n 个子串都是答案，就会沿链转移 n 次，理论复杂度为 O(n*q)。

那为什么在实际数据分布下使用 AC 自动机没有超时，甚至比 Trie 树更快？

这需要分析复杂度推导过程的关键假设：n个子串都是q个询问的答案时，复杂度会退化为O(n*q)。

假设q个询问串都相同，长度为l=L/q。包含#的子串数量约为l²/4。
子串长度之和为 L 时，不同子串数量n≈3/2*L²/³。
两者相等时，l=√6*L¹/³，q=L²/³/√6。

复杂度计算：

n*q = 3/2*L²/³ * L²/³/√6 ≈ 3*L⁴/³

因此复杂度约为O(L^{4/3})，低于O(L²)和O(L√L)，在实际数据规模下通常不会超时。

四、fail 链前缀和优化

如下面的代码，这个算法之所以退化为 O(n*q)，是由于 AC 自动机匹配过程中，需要去 fail 链上不断地遍历。

ll query(const int root, char t[]) {
  int u = root;
  ll res = 0;
  for (int i = 0; t[i]; i++) {
    u = tr[u].son[Hash(t[i])];  // 转移
    // 沿 fail 链累加，终止条件为回到当前 automaton 的 root
    for (int j = u; j != root; j = tr[j].fail) {
      res += tr[j].cnt;
    }
    // 如果 root 本身也为模式结尾（极少见），也需要计入
    if (tr[root].cnt) res += tr[root].cnt;
  }
  return res;
}

而 AC 自动机是静态的，每个节点的 fail 链路径是固定的。

一个显而易见的优化是：预处理每个节点沿 fail 链的累加计数（可视作”前缀和”），从而可以 O(1) 得到该节点所有失败路径上的匹配数。
如下面的代码，使用记忆化搜索的方式实现，初始化代价线性，查询摊还为 O(1)。

int UpPre(int p) {
  if (tr[p].preFlag) return tr[p].preCnt;
  tr[p].preFlag = 1;
  return tr[p].preCnt = tr[p].cnt + UpPre(tr[p].fail);
}
ll query(const int root, char t[]) {
  int u = root;
  ll res = 0;
  for (int i = 0; t[i]; i++) {
    u = tr[u].son[Hash(t[i])];  // 转移
    // 沿 fail 链累加，终止条件为回到当前 automaton 的 root
    res += UpPre(u);
    // for (int j = u; j != root; j = tr[j].fail) {
    //   res += tr[j].cnt;
    // }
    // 如果 root 本身也为模式结尾（极少见），也需要计入
    // if (tr[root].cnt) res += tr[root].cnt;
  }
  return res;
}

此时，每个查询的复杂度就是查询串的长度，总查询的复杂度就固定为 O(L)。

五、最后

感谢 HY-Y 同学与 qwqss 同学留言与我探讨这个问题。

在探讨这个问题的过程中，为了证明这个复杂度，我逐步分析了字符串的特征，对复杂度推导有了更深的理解。
而前缀和优化，更是最关键的一个环节：它把原本可能在失败链上逐节点累加的过程，压缩为常数时间的查询，从而将总复杂度稳定到 O(L) 级别。

以后对于静态数据结构，都可以思考是否尽可能预处理，来降低后续查询的复杂度。

《完》

-EOF-

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

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

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

置顶文章

tiankonguse + ≡
穿越