本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-07-25 23:08:59

首黑祭。
考察：AC 自动机，树状数组，线段树，差分，常数优化。
题目简述：
小 Z 收到了一个字符串 $s$ 及一坨字符串 $\{p_n\}$，求每个 $p_i$ 在 $s$ 中出现的次数。

字符串 $t$ 在字符串 $s$ 中出现的次数定义是 $s$ 中的不同的子串 $s'$ 满足 $s'\pprox t$ 的个数。

$s$ 中的子串 $s'$ 不同指 $s'$ 在 $s$ 中出现的位置不同，即左右端点有一个不同。

$s\pprox t$ 指：

1. $|s|=|t|$
2. $\forall i,j\in[1,|s|]\cap\mathbb Z,s_i\ne t_i,s_j\ne t_j,|i-j|<k$

数据范围：

• $|s|\le 2\times 10^5$
• $\sum_{i=1}^n|p_i|\le2\times 10^5$

我们把 $s\pprox t$ 的定义翻译一下，即：

1. $|s|=|t|$
2. $\text{lcp}(s,t)+\text{lcs}(s,t)+k\ge|s|$

   这里，函数 $\text{lcp}(s,t)$ 指的是 $s$ 和 $t$ 的最长公共前缀，$\text{lcs}(s,t)$ 指的是 $s$ 和 $t$ 的最长公共后缀。

这就出现了类多模字符串匹配，掏出我们的 AC 自动机。$\forall i\in[1,n]\cap\mathbb Z$，将 $p_i$ 和 $p_i$ 的反串（包括 $s$ 和 $s$ 的反串，但为了卡常加入它们时可以不新建节点）扔进 AC 自动机里，然后算 $lst$（其实就是 $fail$，不过我不习惯用它，目的是为了避免与某些稀奇古怪的函数冲突的可能性）指针，建立 $lst$ 树。
如果 $p_i$ 与 $s$ 前缀恰好匹配到了第 $j$ 位，那么后缀至少要匹配到 $j+k+1$ 位。
注意到恰好不好计算，我们就采用差分思想。
若 $p_i$ 的第 $j$ 位在 AC 自动机上的节点是 $u$，反串 $j+k+1$ 位是 $v$，在 $s$ 上与之对应的左右端点分别是 $x,y$，那么需要满足 $x$ 在 $u$ 的子树中且 $y$ 在 $v$ 的子树中。
那么我们遍历整棵树，将询问和修改挂到树上做就可以了，具体实现见代码。

代码