首页 > 代码库 > luogu P3808 【模板】AC自动机(简单版)
luogu P3808 【模板】AC自动机(简单版)
二次联通门 : luogu P3808 【模板】AC自动机(简单版)
/* luogu P3808 【模板】AC自动机(简单版) 手速越来越快了 10分钟一个AC自动机 一遍过编译 + 一边AC 感觉不错 我也就做做板子题了。。 */ #include <iostream> #include <cstring> #include <cstdio> #include <queue> #define Max 1000009 void read (int &now) { register char word = getchar (); for (now = 0; !isdigit (word); word = getchar ()); for (; isdigit (word); now = now * 10 + word - ‘0‘, word = getchar ()); } struct Trie_Data { Trie_Data *child[26]; Trie_Data *Fail; int Count; Trie_Data () { for (int i = 0; i < 26; i ++) this->child[i] = NULL; Fail = NULL; Count = 0; } }; Trie_Data *Root; std :: queue <Trie_Data *>Queue; class AC_Type { public : void Insert (char *key) { Trie_Data *now = Root; Trie_Data *pos; int Id; int Len = strlen (key); for (int i = 0; i < Len; i ++) { Id = key[i] - ‘a‘; if (now->child[Id] == NULL) now->child[Id] = new Trie_Data; now = now->child[Id]; } now->Count ++; } void AC_Build () { Queue.push (Root); Trie_Data *now; Trie_Data *pos; while (!Queue.empty ()) { pos = NULL; now = *&Queue.front (); Queue.pop (); for (int i = 0; i < 26; i ++) { if (now->child[i] == NULL) continue; if (now == Root) now->child[i]->Fail = Root; else { pos = now->Fail; for (; pos; pos = pos->Fail) if (pos->child[i] != NULL) { now->child[i]->Fail = pos->child[i]; break; } if (pos == NULL) now->child[i]->Fail = Root; } Queue.push (now->child[i]); } } } int Query (char *key) { int Answer = 0; int Len = strlen (key); int Id; Trie_Data *now = Root; for (int i = 0; i < Len; i ++) { Id = key[i] - ‘a‘; while (now->child[Id] == NULL && now != Root) now = now->Fail; now = now->child[Id]; if (now == NULL) now = Root; Trie_Data *pos = now; for (; pos != Root && pos->Count >= 0; pos = pos->Fail) { Answer += pos->Count; pos->Count = -1; } } return Answer; } }; AC_Type Make; char line[Max]; int main (int argc, char *argv[]) { int T, N; Root = new Trie_Data; for (read (N); N --; ) { scanf ("%s", line); Make.Insert (line); } Make.AC_Build (); scanf ("%s", line); printf ("%d\n", Make.Query (line)); return 0; }
luogu P3808 【模板】AC自动机(简单版)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。