[bzoj2434]-[NOI2011]阿狸的打字机

ak自动机

题目(BZOJ)

题目(洛谷)

 

来看看这道题吧~

首先我们来想个最暴力的做法:把每个串存起来,然后暴力匹配……复杂度感人.

然后考虑加一点点优化:将这多个串放到一棵Trie上,构建AC自动机,然后像kmp那样匹配……同样感人.

我们来试试其他做法:抽离fail树。

因为在fail树上儿子节点必然可以到father结点,用树状数组维护一个dfs序即可,

具体做法就是:将询问离线,根据每个y去统计每个x,看原串:若为B,则表示退出这个结点,就把这个结点的权值-1;若为P,则表示进入这个结点,就把这个结点的权值+1。

这样就做完了,over

 

发表评论