感觉最近只有我在写博客啊。 这道题的方法是AC自动机+dfs序+树状数组。 你扫描字符串,遇到‘P’就把当前节点设为危险节点,遇到‘B’就返回它的父亲,否则正常转移 于是一个AC自动机就建出来了。 然后你就是跑出以fail数组为连边的树的DFS 离线操作,将询问按y排序, 再次扫描字符串 如果为P, …

这是一道AC自动机QAQ. 题意是求任意两个字符串前缀的最大公共后缀,并且这个后缀要在一个字符串里出现过,输出这个后缀转化成十进制后的答案。 显而易见的是,先建个AC自动机,然后求出fail数组。 你的问题其实就是求两个字符串前缀所在的节点的LCA,然后输出根到它路径上所形成的字符串即可(这个可以预 …

啦啦啦,我这种蒟蒻也只能写这些水题了。 话说czy的模板并不是特别好懂诶@RetardedZY。 这道题其实就是你先把这些合法字符串放进AC自动机。 由于要求的是长度为m的包涵其中一个合法字符串的方案数, 则你可以用AC自动机求出不合法的方案数, 然后用总方案数减去它就可以了。 代码也很短。 Cod …