AC自动机 就是一个多子串匹配的东西，哪有那么厉害，和kmp一样有一个fail指针（下面代码打错了。。，不改了），匹配失败了就跳到file指针，因为fail指针都是从父节点的fail指针推过来的，这样就可以保证前面是一样的了。

AC自动机分三步，第一步是建trie树，第二步是建fail指针（最关键的一步，否则就和字典树一样了），第三步是匹配。

1.建trie图

很容易就建完了。

2.建fail指针

相对较难理解的

有三个变量（都是编号，不是字符）

1 父节点（就是出队的）

2 子节点（就是父结点的子节点）

3 file指向的节点（就是父节点的fail指针，下面简称1,2,3）

其实就是用队列实现的，先把根节点的子节点入队，在一个个出队，如果3.next[2]有值，出队时将2的fail指针连向3的next[2]，没有就把继续找3的fail，直到fail.next[2]有值，或到了根节点。

3.匹配

有一个变量表示当前字符

遵循两种情况1.原串字符和当前指针匹配，就继续向下去匹配吧2.不匹配，就把当前指针移到当前指针的fail指针上，再继续匹配，直到根节点。

这样AC自动机就完成了

丑陋的代码在这

#include
     
      #include 
      
       #include
       
        #include
        
         #include
         
          #define id(x) x-'a';using namespace std;struct st{    int nex[26];    int file;    int count;    int innn(){        memset(nex, -1, sizeof(nex));        count=0;        file=0;    }}s[9999];int cnt;int ins(char ss[]){    int p=0;    for(int i=0;i
          
           0){ tmp=s[tmp].file; } if(s[tmp].nex[i]!=-1){ tmp=s[tmp].nex[i]; } s[s[x].nex[i]].file=tmp; } } } }int tot;char sr[9999];char sh[999];int n;int pipei(){ int p=0; for(int i=0;i
           
            0&&s[p].nex[x]==-1){ p=s[p].file; } if(s[p].nex[x]!=-1){ p=s[p].nex[x]; // tot+=s[p].count; // s[p].count=0; int ind=p; while(ind > 0 && s[ind].count != -1) { tot += s[ind].count; s[ind].count = -1; ind = s[ind].file; } } } printf("%d",tot); return 0;}int main(){ gets(sr); s[0].innn();cnt=1; scanf("%d\n",&n); while(n--){ scanf("%s",sh); //printf("%s\n",sh); ins(sh); } make_file(); pipei();}