【AC自动机】HDU2222 Keywords Search

初学AC自动机。。听说这是入门题就来A了。。

大意:给你n个单词和一个串,问你其中有多少个单词在串中出现过。

这道题还是有坑的。。

1.问的是有多少单词出现过,不是问所有单词总共出现过多少次

2.可能有相同的单词

先讲一下正常的AC自动机算法:

1.先把所有单词建一颗trie树;

2.像KMP一样在trie树上构建fail指针(具体来说,就是从根节点开始BFS,然后每个点从它父亲的fail开始一直往上找fail,如果有结点有和该结点一样字母的儿子那么fail指向其儿子。);

3.扫一遍原串,从根节点往下走,如果能继续匹配就继续匹配,不能继续就跳到fail再试,直到跳到根节点为止。每走过一个结点,该点次数标记++;

4.逆着BFS序,每个点将它的次数标记加给它的fail的次数标记,然后若当前点为关键字点,那么该点所对应的次数标记为这个单词的出现次数。

写了一个自认为很简明的AC自动机模板:

那么这道题,只要改两个地方:把次数换成bool类型,然后记一下重复单词次数就行了。

代码写得有点丑,因为这个是先写的XD:

说点什么

您将是第一位评论人!

提醒
wpDiscuz