BUG传送门：布呗之路
分析：分享在B站上看到的一个AC自动机的一种思想，其实个人感觉这种写法还是不错的，思想挺好的；
#include <iostream> #include <algorithm> #include <map> #include <stack> #include <queue> #include <set> #include <vector> #include <cstdlib> #include <cmath> #include <string> #include <cstdio> #include <cstring> #define ll long long #define ull unsigned long long #define PI acos(-1.0) #define inf 0x3f3f3f3f #define E 2.7182818284590452353602874713527 using namespace std; const int maxn=1e6+7; const int max_tot=5e5+7; struct Trie{ struct node{ int Next[26]; int fail,cnt; }a[max_tot]; int size; queue<int>que; ///对于每一个节点的各类信息进行初始化操作； void init(){ while(!que.empty()) que.pop(); for(int i=0;i<max_tot;i++){ memset(a[i].Next,0,sizeof(a[i].Next)); a[i].fail=a[i].cnt=0; } size=1; } void insert(char buf[]){ int len=strlen(buf); int now=0; for(int i=0;i<len;i++){ if(!a[now].Next[buf[i]-'a']){ a[now].Next[buf[i]-'a']=size++;//如果节点不存在的话，另开节点； } now=a[now].Next[buf[i]-'a'];//不断的移动至下一个节点； } a[now].cnt++;//单词最后一个节点，代表一个单词 } void build(){ //先将root入队； a[0].fail=-1; que.push(0); while(!que.empty()){ int u=que.front(); que.pop();//弹出队节点 ，对于队头节点的26个子节点进行遍历; for(int i=0;i<26;i++){ if(a[u].Next[i]){//找到实际存在的字符节点 if(u==0){//如果是第一层的字符节点，则把该节点的fail指向root=0； a[a[u].Next[i]].fail=0; } else { //依次回溯该节点的祖先，直到当前节点与某节点的next[i]相同； int v=a[u].fail; while(v!=-1){ if(a[v].Next[i]){ a[a[u].Next[i]].fail=a[v].Next[i]; break; } v=a[v].fail; } //回溯完成后发现不存在next[i]相等的话，则赋值为0； if(v==-1){ a[a[u].Next[i]].fail=0; } } que.push(a[u].Next[i]); } } } } //记录以now为终点的路径上字符串的个数； int get_sum(int now){ int ans=0; while(now!=-1){ ans+=a[now].cnt; a[now].cnt=0; now=a[now].fail; } return ans; } ///利用失配函数进行字符串的匹配； int math(char buf[]){ int len=strlen(buf); int ans=0,now=0; for(int i=0;i<len;i++){ if(a[now].Next[buf[i]-'a']){ now=a[now].Next[buf[i]-'a']; } else { int p=a[now].fail; while(p!=-1&&a[p].Next[buf[i]-'a']==0){ p=a[p].fail; } if(p==-1){ now=0; } else{ now=a[p].Next[buf[i]-'a']; } } ///如果这个点存在单词的话 if(a[now].cnt){ ans+=get_sum(now); } } return ans; } }; char s[maxn]; Trie ac; int main (){ int t; cin>>t; while(t--){ ac.init(); int n; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%s",s); ac.insert(s); } ac.build(); scanf("%s",s); printf("%d\n",ac.math(s)); } return 0; }