2434: [Noi2011]阿狸的打字机

首先容易根据给出的字符串建出trie树

对于查询(x,y),相当于对于y的每一个位置求出他的后缀是否包含x串

那么容易想到建立出ac自动机。

那么就是对于y串的每个位置,其能否通过fail到达x所在节点。

发现其实fail指针会构成一棵树,那么相当于统计在x节点下有多少点属于y串。

发现如果直接枚举是O(n^2),那么考虑dfs trie树,记录每个位置是否是y串,

然后查询其对应x串下子树有多少节点是y串节点,然后这个东西容易发现可以直接通过dfs序用树状数组维护

此时复杂度为O(nlog n)

搞定.

c++代码如下:

 

8 + 9 =