[BZOJ3172/Luogu3966][TJOI2013]单词(AC自动机)

发布于 2018-03-20  156 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3172/Luogu3966][TJOI2013]单词(AC自动机)

Description

某人读论文,一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次,现在想知道每个单词分别在论文中出现多少次。

Tag

AC自动机

解决思路

考虑在AC自动机中如何处理一个问题,一个字符串x出现在另一个字符串y中的某一位置,当且仅当这个位置的结尾可以通过跳Fail跳到x的结尾。
把问题放到Fail树上考虑,就变成了统计Fail树上每一个点的子树大小,一遍dfs扫描。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3172/Luogu3966][TJOI2013]单词(AC自动机)


HNCJ OIer