要点
这是一道蔡队题，看我标题行事- 任意询问y串上有多少个x串，暴力找每个节点是不是结尾肯定是炸的，考虑本质：如果某节点是x的结尾，根据ac自动机的性质，x一定是此（子）串后缀。又有每个Trie节点的fail只指向另一个节点，故有fail树的概念。问题就变成了任意询问y串上有多少个x串，暴力找每个节点
阅读背景：
洛谷2414（构建ac自动机fail树dfs序后遍历Trie树维护bit及询问答案）
来源：互联网
分享到：
