板子题
找模式串T中出现了多少个匹配串P
#include<bits/stdc++.h> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int MAX_N=1e6+10; const int MAX_Tot=5e5+10; struct Aho{ struct state{ int next[26]; int fail,cnt; }stateTable[MAX_Tot]; int siz; queue<int> que; void init(){ while(que.size()) que.pop(); for(int i=0;i<MAX_Tot;i++){ memset(stateTable[i].next,0,sizeof(stateTable[i].next)); stateTable[i].fail=stateTable[i].cnt=0; } siz=1; } void inserts(char *S){ int n=strlen(S); int now=0; for(int i=0;i<n;i++){ char c=S[i]; if(!stateTable[now].next[c-'a']) stateTable[now].next[c-'a']=siz++; now=stateTable[now].next[c-'a']; } stateTable[now].cnt++; } void build(){ stateTable[0].fail=-1; que.push(0); while(que.size()){ int u=que.front(); que.pop(); for(int i=0;i<26;i++){ if(stateTable[u].next[i]){ if(!u) stateTable[stateTable[u].next[i]].fail=0; else{ int v=stateTable[u].fail; while(v!=-1){ if(stateTable[v].next[i]){ stateTable[stateTable[u].next[i]].fail=stateTable[v].next[i]; break; } v=stateTable[v].fail; } if(v==-1) stateTable[stateTable[u].next[i]].fail=0; } que.push(stateTable[u].next[i]); } } } } int Get(int u){ int res=0; while(u){ res=res+stateTable[u].cnt; stateTable[u].cnt=0; u=stateTable[u].fail; } return res; } int match(char *S){ int n=strlen(S); int res=0,now=0; for(int i=0;i<n;i++){ char c=S[i]; if(stateTable[now].next[c-'a']) now=stateTable[now].next[c-'a']; else{ int p=stateTable[now].fail; while(p!=-1&&stateTable[p].next[c-'a']==0) p=stateTable[p].fail; if(p==-1) now=0; else now=stateTable[p].next[c-'a']; } if(stateTable[now].cnt) res=res+Get(now); } return res; } }aho; char s[MAX_N]; int main() { int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); aho.init(); for(int i=0;i<n;i++){ scanf("%s",s); aho.inserts(s); } aho.build(); scanf("%s",s); printf("%d\n",aho.match(s)); } return 0; }
