二次聯通門 :?luogu P3808 【模板】AC自動機（簡單版）

?

?

?

?

/*luogu P3808 【模板】AC自動機（簡單版）手速越來越快了10分鐘一個AC自動機一遍過編譯 + 一邊AC感覺不錯我也就做做板子題了。。*/ #include <iostream> #include <cstring> #include <cstdio> #include <queue>#define Max 1000009void 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; }

?

轉載于:https://www.cnblogs.com/ZlycerQan/p/7341480.html

總結

以上是生活随笔為你收集整理的luogu P3808 【模板】AC自动机（简单版）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。