本文共 1286 字，大约阅读时间需要 4 分钟。

题中有一个坑点，就是模式串可以相同，并且全部计数。

#include 
   
    using namespace std;const int maxn=1e6+10;const int N=maxn;char str[maxn];struct Dfa {
   	int trie[N][26],cnt;	int e[N];	int fail[N];	char ch;		void init(char c) {
   		memset(trie,0,sizeof(trie));		memset(e,0,sizeof(e));		memset(fail,0,sizeof(fail));		cnt=0;		ch=c;	}		void insert(char * s) {
   		int p=0;		for (int i=0;s[i];i++) {
   			int to=s[i]-ch;			if (trie[p][to]==0) {
   				trie[p][to]=++cnt;			}			p=trie[p][to];		}		e[p]++;	}		void build() {
   		queue
    
      q;		for (int i=0;i<26;i++) {
   			if (trie[0][i]) {
   				q.push(trie[0][i]);			}		}				while (!q.empty()) {
   			int root=q.front();			q.pop();			for (int i=0;i<26;i++) {
   				if (trie[root][i]) {
   					fail[trie[root][i]]=trie[fail[root]][i];					q.push(trie[root][i]);				}				else {
   					trie[root][i]=trie[fail[root]][i];				}			}		}		}		long long query(char * s) {
   		long long ans=0;		int p=0;		for (int i=0;s[i];i++) {
   			p=trie[p][s[i]-ch];//第一层的空节点k trie[0][k]=0 			for (int j=p;j&&~e[j];j=fail[j]) {
   				ans+=e[j];				e[j]=-1;			}		}		return ans;	}}dfa;int main(){
   	int n;	dfa.init('a');	scanf("%d",&n);	while (n--) {
   		scanf("%s",str);		dfa.insert(str);	}	dfa.build();	scanf("%s",str);	printf("%lld\n",dfa.query(str));	return 0;}
    
   

转载地址：http://cruen.baihongyu.com/