关于 AC 自动机的字符串匹配

学术版

sbno333 @ 2024-11-28 14:42:07

题目：给定 n 个模式串，q 个文本串，求对于每一个文本串有几个模式串为其子串。

能不能 q 次询问文本串每一次复杂度都只关于文本串？

by bladrrxy @ 2024-11-28 14:58:59

fail 树上前缀和，计算出 s_u 表示结点 u 到根的链上有几个结点是完整的模式串。

每次把文本串匹配得到的结点按 fail 树上 dfn 排序，从小到大加入结点，每次加上 s_{a_i}，减去 s_{lca(a_i, a_{i - 1})}。

（验证码666G

by 262620zzj @ 2024-11-28 19:59:16

@bladrrxy按dfn排序妙啊

by bladrrxy @ 2024-11-28 20:55:04

@262620zzj P2336 就是这么做的。