题目大意：
给定$n$个模式串$p(sum|p_i|le10^6)$和一个$t(|t|le10^6)$，求在$t$中被匹配的$p$的个数。
思路：
AC自动机模板题，注意$t$中一个字符可能对应自动机上多个结点，因此需要按照失配指针跳转统计。统计过的结点需要特殊标记，避免重复统计，否则会超时。
1 #include<queue> 2 #include<cstdio> 3 #include<cctype> 4 inline int getint() { 5 register char ch; 6 while(!isdigit(ch=getchar())); 7 register int x=ch^'0'; 8 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 9 return x; 10 } 11 const int N=1e6+1,S=26; 12 char s[N]; 13 int ans=0; 14 class AhoCorasick { 15 private: 16 std::queue<int> q; 17 int val[N],ch[N][S],fail[N]; 18 int sz,new_node() { 19 return ++sz; 20 } 21 int idx(const char &c) const { 22 return c-'a'; 23 } 24 public: 25 void insert(const char s[]) { 26 int p=0; 27 for(register int i=0;s[i];i++) { 28 if(!ch[p][idx(s[i])]) ch[p][idx(s[i])]=new_node(); 29 p=ch[p][idx(s[i])]; 30 } 31 val[p]++; 32 } 33 void get_fail() { 34 for(register int i=0;i<S;i++) { 35 if(ch[0][i]) q.push(ch[0][i]); 36 } 37 while(!q.empty()) { 38 const int &x=q.front(); 39 for(register int i=0;i<S;i++) { 40 if(!ch[x][i]) { 41 ch[x][i]=ch[fail[x]][i]; 42 continue; 43 } 44 fail[ch[x][i]]=ch[fail[x]][i]; 45 q.push(ch[x][i]); 46 } 47 q.pop(); 48 } 49 } 50 void find(const char s[]) { 51 int p=0; 52 for(register int i=0;s[i];i++) { 53 p=ch[p][idx(s[i])]; 54 for(register int q=p;q&&~val[q];q=fail[q]) { 55 ans+=val[q]; 56 val[q]=-1; 57 } 58 } 59 } 60 }; 61 AhoCorasick ac; 62 int main() { 63 const int n=getint(); 64 for(register int i=0;i<n;i++) { 65 scanf("%s",s); 66 ac.insert(s); 67 } 68 ac.get_fail(); 69 scanf("%s",s); 70 ac.find(s); 71 printf("%d ",ans); 72 return 0; 73 }