P3735 [HAOI2017] 字符串 题解

zrl123456 · 2025-07-25 23:08:59 · 题解

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

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

$s\approx 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\approx 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 的子树中。
那么我们遍历整棵树，将询问和修改挂到树上做就可以了，具体实现见代码。

代码