BZOJ 3172 [Tjoi2013] 单词

发布于 2017-07-02  110 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3172

题意:给出一个字典,问字典中的每个单词在整个字典中出现了多少次。


人生中的第一次 AC 自动机?

考虑朴素的暴力:建立 AC 自动机后依次查询每个串,为经过的节点加一出现次数。

然而此题有个特殊的性质:即文本串=字典

这有什么用呢?最直观的,每个单词的尾节点都可以沿着 fail 链更新答案上去,更本质地:一个节点的父节点一定在儿子节点中出现了

所以我们在建立 trie 树时可以为每个节点都累计一个“出现次数”,对于每个节点,沿着 fail 指针向上更新,按照建立 fail 指针的逆序即可

最后累计在每个尾节点上的出现次数即为每个串的答案

 


一个非常弱的准退役OIER