首页 > 代码库 > [BZOJ 3172] [Tjoi2013] 单词 【AC自动机】
[BZOJ 3172] [Tjoi2013] 单词 【AC自动机】
题目链接：BZOJ - 3172
题目分析：
题目要求求出每个单词出现的次数，如果把每个单词都在AC自动机里直接跑一遍，复杂度会很高。
这里使用AC自动机的“副产品”——Fail树，Fail树的一个性质是，一个字符串出现的次数，就等于以它的结点为根的Fail树中的子树中所有结点的 Cnt 和。
所以把每个单词插入的时候每个字符都 ++Cnt ，在建 Fail 的时候将结点依次压入一个栈，最后再从栈顶开始弹栈，更新栈顶元素的 Fail 的 Cnt 值，这样就是自叶子节点向上更新了。
我开始写的时候出现的错误：建 Fail 的时候漏掉了 if (Now -> Child[i] == NULL) Now -> Child[i] = Now -> Fail -> Child[i]; 这句。这样会 RE ！
代码如下：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm> using namespace std; const int MaxN = 200 + 5, MaxL = 1000000 + 5, MaxC = 26; int n, l; char Str[MaxL]; struct Trie { int Cnt; Trie *Fail, *Child[MaxC]; void clear() { Cnt = 0; Fail = NULL; for (int i = 0; i < 26; ++i) Child[i] = NULL; }} TA[MaxL], *P = TA, *Root, *Zero, *Pos[MaxN]; Trie *NewNode() { ++P; P -> clear(); return P;} void AC_Init() { Zero = NewNode(); Root = NewNode(); Root -> Fail = Zero; for (int i = 0; i < 26; ++i) Zero -> Child[i] = Root;} Trie *Insert(char *Str, int l) { Trie *Now = Root; int t; for (int i = 0; i < l; ++i) { t = Str[i] - ‘a‘; if (Now -> Child[t] == NULL) Now -> Child[t] = NewNode(); Now = Now -> Child[t]; ++(Now -> Cnt); } return Now;} Trie *Q[MaxL], *S[MaxL];int Head, Tail, Top; void Build_Fail() { Top = 0; Head = Tail = 0; Q[++Tail] = Root; Trie *Now; while (Head < Tail) { Now = Q[++Head]; S[++Top] = Now; for (int i = 0; i < 26; ++i) { if (Now -> Child[i] == NULL) Now -> Child[i] = Now -> Fail -> Child[i]; else { Now -> Child[i] -> Fail = Now -> Fail -> Child[i]; Q[++Tail] = Now -> Child[i]; } } } while (Top) { Now = S[Top--]; if (Now -> Fail != NULL) (Now -> Fail -> Cnt) += (Now -> Cnt); }} int main() { scanf("%d", &n); AC_Init(); for (int i = 1; i <= n; ++i) { scanf("%s", Str); l = strlen(Str); Pos[i] = Insert(Str, l); } Build_Fail(); for (int i = 1; i <= n; ++i) printf("%d\n", Pos[i] -> Cnt); return 0;}
[BZOJ 3172] [Tjoi2013] 单词 【AC自动机】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。