AC自动机

 

一、实质：多模式字符串匹配

二、主要步骤

　　1.将所有模式串构建一棵Trie树

　　2.对Trie上所有的节点构造前缀指针

　　3.利用前缀指针对主串进行匹配

三、算法流程　　

　　1.建立Trie树

　　2.主串和模式串匹配

　　3.建立next数组

四、操作实现

#include<bits/stdc++.h>
#define N 500010
using namespace std;
queue<int>q;
struct Aho_Corasick_Automaton{
    int c[N][26],val[N],next[N],cnt;
    void ins(char *s)
    {
        int len=strlen(s);int u=0; 
        for(int i=0;i<len;i++)
        {
            int v=s[i]-'a';
            if(!c[u][v]) c[u][v]=++cnt;
            u=c[u][v];
        }
        val[u]++;
    }
    void build()
    {
        for(int i=0;i<26;i++) if(c[0][i]) next[c[0][i]]=0,q.push(c[0][i]);
        while(!q.empty())
        {
            int u=q.front();q.pop();
            for(int i=0;i<26;i++)
                if(c[u][i])    next[c[u][i]]=c[next[u]][i],q.push(c[u][i]);
                else c[u][i]=c[next[u]][i];
        }
    }
    int query(char *s){
        int len=strlen(s);int u=0,ans=0;
        for(int i=0;i<len;i++)
        {
            u=c[u][s[i]-'a'];
            for(int t=u;t&&~val[t];t=next[t])ans+=val[t],val[t]=-1;
        }
        return ans;
    }
}AC;
int n;char p[1000005];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%s",p),AC.ins(p);
    AC.build();
    scanf("%s",p),printf("%d",AC.query(p));
    return 0;
}