P2414 [NOI2011] 阿狸的打字机
题解
显然直接做没法做,考虑一些转化。
由于:
- X 是 Y 的一个子串等价于 X 是 Y 的某个前缀的后缀。
- 在 Trie 树上,一个节点的所有祖先节点是它的所有前缀。
- 在 Fail 树(fail 指针反向连接而成)上,一个节点的所有祖先节点为其所有后缀。
因此,X 是 Y 的某个后缀的前缀等价于 Fail 树中,以 X 作为某个祖先的节点,同时是 Y 在 Trie 树的祖先的节点数。
换句话说,我们要求 Fail 树中 X 的子树与 Trie 树中 Y 的父节点的公共节点数。
由子树很容易想到 DFS 序,所以我们对 Fail 树用 DFS 转换成区间。
这样,我们只需要对于每个 Y,统计其所有祖先节点在某个区间的个数,容易想到用树状数组维护,具体的,用 DFS 遍历 Trie 树,将当前节点祖先在树状数组的对应位置 +1,对于每个 Y 查询 X 对应区间即可,回溯时在树状数组上 −1。
