ac자동기(템플릿+조금씩 최적화)

#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1000005;//     
struct ac_auto{
    const static int letter_size = 26;
    const static int trie_size = (1e6+50);
    int tot , root ,fail[trie_size],end[trie_size],next[trie_size][letter_size];
    int newnode()
    {
        end[tot]=0;
        memset(next[tot],-1,sizeof next[tot]);
        return tot++;
    }
    void init()
    {
        tot=0;
        root=newnode();
    }
    int getidx(char x){
        return x-'a';
    }
    void insert(char ss[])//    
    {
        int len=strlen(ss);
        int now=root;
        for(int i=0;iint id=getidx(ss[i]);
            if(next[now][id]==-1)
            {
                next[now][id]=newnode();
            }
            now=next[now][id];
        }
        end[now]++;
    }
    void getfail()//  fail  
    {
        queue<int>q;
        fail[root]=root;
        for(int i=0;i//   
        {
            if(next[root][i]!=-1)
            {
                fail[next[root][i]]=root;
                q.push(next[root][i]);
            }
            else
            {
                next[root][i]=root;
            }
        }
        while(!q.empty())
        {
            int now=q.front();q.pop();
            for(int i=0;iif(next[now][i]!=-1)
                {
                    fail[next[now][i]]=next[fail[now]][i];//   next[now][i]       , fail          。
                    q.push(next[now][i]);
                }
                else next[now][i]=next[fail[now]][i];//    next[now][i]    ，         
            }
        }
    }
    int match(char ss[])
    {
        int sum=0,now=root;
        int len=strlen(ss);
        for(int i=0;iint id=getidx(ss[i]);
            int tmp=now=next[now][id];
            while(tmp)
            {
                //   
                //if(end[tmp]！=-1)
                //res += end[tmp];
                //  
                if(end[tmp]==-1)break;//       
                sum+=end[tmp];
                end[tmp]=-1;
                tmp=fail[tmp];
            }
        }
        return sum;
    }

};
ac_auto ac;
char ss[maxn];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        ac.init();
        for(int i=0;iscanf("%s",ss);
            ac.insert(ss);
        }
        ac.getfail();
        scanf("%s",ss);
        printf("%d
",ac.match(ss));
    }
    return 0;
}