有一台打字机: - 输入小写字母, 该字母入栈 - 按一下 'B', 最后一个字母弹栈 - 按一下 'P', 从栈底到栈顶打印字母并换行, 不修改栈
给出输入序列, 设打印出 n 个字符串, 现有 m 个询问: 第 x 个打印的字符串在第 y 个打印的字符串中出现了多少次? (1 ≤ n,m ≤ 10^5, |输入序列| ≤ 10^5) 用 Trie 树存储字符串, 每个询问用 KMP 暴力, 就有50分了.
考虑 AC 自动机上一条 fail 边 (u,v) 的意义: v 是 u 的最长真后缀. 那么, 如果 u 可以顺着 fail 边直接或间接走到 v, 说明 v 作为 u 的某个后缀出现了一次. 反之亦然.
建出 AC 自动机. 一个询问 (x,y) 等价于: Trie 树的 root - y 链上有多少个点可以直接或间接走到 x ? 用 fail 边建出一棵fail 树, 如果我们能标记出哪些点在 Trie 树的某条链上, 那么借助于 DFS 序 + 某种支持动态修改和区间查询的数据结构 (如树状数组), 便能回答询问.
离线. 先扫一遍输入序列, 建出 AC 自动机及 fail 树, 然后把询问 (x,y) 挂在节点 y 上再跑一遍, 这次每到一个点就在树状数组上标记它, 离开这个点就取消它的标记.
去年寒假贺神回来教我们 KMP 和 AC 自动机 QwQ 这是我去年学 AC 自动机的时候做的第一道题, 因为 CodeVS 里只有这道题......过了好久终于看懂了题解 (然而黄学长说这是不用动脑子的题!), 通过这道题学到什么是离线化, 什么是树状数组, 什么是 DFS 序......
缺乏科学的学习方法是一件很坑的事啊...... >_<