1 #include<iostream>  2 #include<string>  3 #include<queue>  4 using namespace std;  5   6   7   8   9 struct trie{ 10     int count; 11     trie *fail; 12     trie *son[26]; 13     trie() 14     { 15         count=0; 16         fail=nullptr; 17         for(int i=0;i<26;i++) 18             son[i]=nullptr; 19     } 20 }; 21 queue<trie*> q; 22 trie *root; 23  24 string target; 25  26 int query() 27 { 28     int count=0; 29     trie* temp=root; 30     int len=target.length(); 31     for(int i=0;i<len;i++) 32     { 33         int pos=target[i]-‘a‘; 34         if(temp->son[pos]==nullptr) 35         { 36             while(temp->son[pos]==nullptr && temp!=root) 37             { 38                 temp=temp->fail; 39             } 40         }     41         temp=temp->son[pos];             42         if(temp==nullptr) 43             temp=root; 44         trie *p=temp; 45         while(p!=root && p->count!=-1) 46         { 47             count+=p->count; 48             p->count=-1; 49             p=p->fail; 50         }         51     } 52     return count; 53      54 } 55  56  57 void build_ac() 58 { 59     int start=0; 60     int end=0; 61     q.push(root); 62     while(!q.empty()) 63     { 64         trie *temp=q.front(); 65         q.pop(); 66         for(int i=0;i<26;i++) 67         { 68             if(temp->son[i]!=nullptr) 69             { 70                 if(temp==root) 71                 { 72                     temp->son[i]->fail=root; 73                     q.push(temp->son[i]); 74                     continue; 75                 } 76                 trie *f_fail=temp->fail; 77                 while(f_fail!=nullptr) 78                 { 79                     if(f_fail->son[i]!=nullptr) 80                     { 81                         temp->son[i]->fail=f_fail->son[i]; 82                         break; 83                     } 84                     f_fail=f_fail->fail; 85                 } 86                 if(f_fail==nullptr) 87                     temp->son[i]->fail=root; 88                 q.push(temp->son[i]); 89             } 90  92         } 93     } 94 } 95  96 void insert(string str) 97 { 98     int len=str.length(); 99     trie *temp=root;100     for(int i=0;i<len;i++)101     {102         int pos=str[i]-‘a‘;103         if(temp->son[pos]==nullptr)104             temp->son[pos]=new trie();105         temp=temp->son[pos];106     }107     temp->count++;     108     109 }110 111 int main()112 {113     int n;114     cin>>n;115     root=new trie();116     for(int i=0;i<n;i++)117     {118         string str;119         cin>>str;120         insert(str);121     }122     build_ac();123     cin>>target;124     int ret=query();125     cout<<ret<<endl;126 }