【习题选讲】字符串

imily's notebook

2020-07-09

AC自动机

[POJ3167]

KMP + 树状数组，注意细节

套路好题（

首先有个性质：AC自动机 fail 树上的父亲节点是子节点的子串。

然后就有个经典套路：AC自动机上找一个串的出现次数可以在 fail 树上跑。

将询问离线，从小到大插入 AC 自动机（插入方法是节点 val = 1），树状数组维护 dfs 序算询问点子树中 1 的个数。

考虑在 Trie 上做。然后就变成一棵有许多黑点的 Trie 树，要将黑点尽可能地放到祖先节点去。

优先队列维护，优先放原本深度大的点。

KMP 性质题。AC 自动机上找串出现次数可以跑 fail 树，但本题要所有前缀，会TLE。

考虑 fail 指针意义，设计 DP：f[i] 表示以 i 结尾的所有前缀个数，f[i] = f[fail[i]] + 1.

套路题直接上 01 trie，值得注意的是：本题 n^3 会 TLE，因为重复插入了很多串； n^2 枚举 i 和 j 再减掉 Trie 中 i 和 j 串的贡献就可以过啦。

总结：