题目分析

问题本质

维护动态字符串集合 $T$，支持：

• 添加字符串 $P$ 到集合 $T$
• 查询集合 $T$ 中有多少字符串包含固定模式串 $S_x$

核心挑战

1. 高效子串匹配：快速判断 $S_x$ 是否是 $T$ 中字符串的子串
2. 动态更新：$T$ 集合不断增长，需要支持增量处理
3. 大规模数据：$n,q \leq 10^5$，总字符串长度 $\leq 2\times 10^6$

关键观察

问题转化

查询"$T$ 中有多少字符串包含 $S_x$"等价于：

• 对于每个添加到 $T$ 的字符串 $P$，检查 $S_x$ 是否是 $P$ 的子串
• 但直接对每个查询扫描所有 $P$ 不可行

AC自动机的性质

AC自动机的fail树具有重要性质：

• 如果节点 $u$ 对应某个字符串的结束位置，那么fail树上 $u$ 到根路径上的所有节点对应的字符串都是当前匹配串的子串

算法框架

解法：AC自动机 + 树状数组 + 树链剖分

步骤1：预处理Alice的字符串

1. 对所有 $S_1, S_2, \ldots, S_n$ 建立AC自动机
2. 构建fail树（每个节点的fail指针形成的树结构）
3. 为fail树分配DFS序，便于区间操作

步骤2：数据结构准备

• 树状数组：维护fail树上节点的标记信息
• 每个 $S_i$ 在AC自动机中对应一个结束节点

步骤3：处理添加操作 1 P 当添加字符串 $P$ 时：

1. 在AC自动机上匹配 $P$
2. 对于匹配过程中经过的每个节点 $u$，在fail树上标记从 $u$ 到根的路径
3. 这表示 $P$ 包含了这些节点对应的所有 $S_i$

具体实现：

• 匹配 $P$ 时，记录经过的所有节点
• 对这些节点在fail树上的所有祖先进行标记
• 使用树链剖分 + 树状数组高效实现路径标记

步骤4：处理查询操作 2 x 查询 $S_x$ 被多少字符串包含：

1. 找到 $S_x$ 在AC自动机中的结束节点 $v$
2. 查询节点 $v$ 在树状数组中的值
3. 这个值就是包含 $S_x$ 的字符串数量

算法细节

AC自动机构建

• 将所有 $S_i$ 插入Trie树
• 构建fail指针，形成fail树
• 记录每个 $S_i$ 的结束节点

树链剖分应用

在fail树上进行树链剖分：

• 将树分成重链，分配DFS序
• 路径标记转化为区间加操作
• 单点查询转化为区间求和

标记传播优化

当匹配字符串 $P$ 时：

• 不需要显式标记所有祖先节点
• 可以利用AC自动机的性质，只标记匹配过程中实际访问的节点
• 通过fail树的传递性自动覆盖所有相关模式串

复杂度分析

时间复杂度

• AC自动机构建：$O(\sum |S_i|)$
• 每次添加操作：$O(|P| \log n)$
  • 匹配字符串：$O(|P|)$
  • 路径标记：$O(\log n)$ 每条路径
• 每次查询操作：$O(\log n)$
• 总复杂度：$O(\sum |S_i| + \sum |P| \log n + q \log n)$

空间复杂度

• AC自动机：$O(\sum |S_i|)$
• 树状数组：$O(\sum |S_i|)$
• 总空间：$O(\sum |S_i|)$

实现技巧

路径标记优化

使用差分思想：

• 在路径的起点打上 $+1$ 标记
• 在路径终点的父节点打上 $-1$ 标记
• 通过子树求和得到每个节点的值

重复处理

如果同一个字符串 $P$ 被多次添加，需要去重或特殊处理。

内存管理

• 使用静态数组存储AC自动机
• 预分配足够空间

替代方案分析

方案2：后缀自动机

• 对 $T$ 中字符串建立广义后缀自动机
• 查询时检查 $S_x$ 是否出现在自动机中
• 但动态添加时重建成本高，不适合本题

方案3：在线算法

• 对每个新加的 $P$，用KMP检查它包含哪些 $S_i$
• 更新对应的计数器
• 复杂度：$O(\sum |P| \cdot \sum |S_i|)$，不可行

方案4：哈希 + 布隆过滤器

• 存储 $T$ 中所有子串的哈希值
• 查询 $S_x$ 的哈希值是否存在
• 空间开销大，可能有误判

特殊情况处理

空字符串

题目保证字符串非空，无需特殊处理。

重复模式串

不同的 $S_i$ 可能是相同的字符串，需要分别计数。

内存限制

总字符串长度 $2\times 10^6$，AC自动机节点数在可接受范围内。

总结

本题的核心在于利用AC自动机的fail树性质，将子串包含问题转化为树上的路径标记问题。通过树链剖分和树状数组，可以高效处理动态添加和查询操作。关键难点在于理解fail树的结构和设计高效的标记传播机制。