【NOI2011】阿狸的打字机


模式串之间相互匹配的问题。

利用 fail 指针,如果结点 \(x\) 的 fail 指针指向 \(y\) ,说明以 \(y\) 为结尾的字符串是 \(x\) 的后缀。

于是原题的询问就变成了有多少个属于\(y\) 的节点的 fail 指针直接或间接指向\(x\) 字符串的结束位置。

于是我们构建 AC 自动机的 fail 树,问题再一次转化为,在 \(x\) 为根节点的子树中,有多少个属于 \(y\) 的结点。

这个问题,我们把树按照 dfs 序拆分到一维,显然,子树是一维中连续的一段。

我们按照所有插入字串的字典序排序,并将询问全部离线,按照被询问主串的字典序排序。

我们进入一个结点的时候打上 \(+1\) 标记,除去的时候把标记取消,当跑到一个结点是一个字符串的结尾的时候,把所有主串为这个字符串的询问全部处理掉。因为此时所有属于这个字符串的结点都有 \(1\) 的标记,我们对所有的询问所对应的区间求和即可。

还有一些需要注意的问题:

  • 同样的字符串可能出现了多次,我把每一个结点的 val 改成了 vector 来存储。
  • 我的模版 getfail 的时候 ch 数组会发生变化,提前备份。
  • 每次暴力插入所有的字符串是要 TLE 的,这道题目的 insert 需要直接在 Trie 树上进行。

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 8,102

Categories

Archive

Comments