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

• 题意
  问一个字符串中包含多少种模式串，该字符串的反向串包含也算。
• 思路
  解析一下字符串，简单。
  建自动机的时候，通过fail指针建立trie图。这样跑图的时候不再跳fail指针，相当于就是放弃了fail指针。
  跑的时候，已经走过的模式串不能二次计数。
• 代码
  附赠一大波样例

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn=5100010;const int N=250010;char cmp[maxn];char dmp[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;			}		}		int len=strlen(s);		p=0;		for (int i=len-1;i>=0;i--) {
   			p=trie[p][s[i]-ch];			for (int j=p;j&&~e[j];j=fail[j]) {
   				ans+=e[j];				e[j]=-1;			}		}		return ans;	}}dfa;void translate(char * c){
   	int cnt=0,x=0;	bool flag=false;	for (int i=0;c[i];i++) {
   		if (c[i]!='['&&c[i]!=']') {
   			if (c[i]>='A'&&c[i]<='Z') {
   				if (flag==false) {
   					dmp[cnt++]=c[i];				}				else {
   					while (x--) {
   						dmp[cnt++]=c[i];					}					x=0;					flag=false;				}			}			else {
   				flag=true;				x=x*10+c[i]-'0';			}		}	}	dmp[cnt]='\0';	//cout<
        
         <
        
       
      
     
    
   

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