【BZOJ2434】【NOI2011】阿狸的打字机

正好今天伦boy讲了这道题 我正好就做到这题 真巧

因为如果A是B的子串那么A是B的某个前缀的后缀

那么建一个AC自动机,对于B的每个前缀也就是B在trie树中的所有父亲打上标记,那么答案就是A在fail树中的子树中的标记个数

按照在trie树中的dfs序依次处理每个B;然后再fail树中用dfs序+树状数组可以快速查询

说点什么

  Subscribe  
提醒