AC自动机

一．Trie 

　　trie是一种查找树，节点每条连向儿子的边表示一个字母，根据单词的字母排列，就能从根节点选择一条路径到达一个节点。不同单词到达不同的节点，每个节点也对应了一个单词。

　　详细介绍，请看：http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries

二．状态机

　　用节点代表状态，有向边代表状态转移，就构成了状态机。

三．AC自动机

　　AC自动机是在一个trie上构造的有限状态机。

　　详细介绍，请见：http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf 

　　　　　　和：http://www.notonlysuccess.com/index.php/aho-corasick-automaton/

　　cdoj上一道题目：http://www.cnblogs.com/luna-lovegood/archive/2012/04/06/2434351.html

　　　下面是我的模板：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<iostream>
using namespace std;
char chrn;
#define SCRN while(scanf("%c",&chrn) && chrn!='\n');

typedef struct
{
    int f,t;//f:最大前缀匹配的点；t：when enter the node,how many patterns are recognised；
    int e[26];
}node;

int N,top,front,rear,queue[10000];
node trie[3000];

void push(int i)
{
    queue[rear++]=i;
}

int pop()
{
    front++;
    return queue[front-1];
}

void ini()
{
    int t;
    top=0;
    trie[0].f=-1;
    trie[0].t=0;
    for(i=0; i<26; i++)
        trie[0].e[i]=-1;
    top++;
}

void insert(int idx,char *s,int len)
{
    int i;
    if(trie[idx].e[s[0]-'A']==-1)
    {
        trie[idx].e[s[0]-'A']=top;
        trie[top].f=0;
        for(i=0; i<26; i++)
            trie[top].e[i]=-1;
        len--;
        if(len==0)
            trie[top++].t=1;
        else
        {
            trie[top].t=0;
            top++;
            insert(top-1,s+1,len);
        }
    }
    else
    {
        len--;
        if(len==0)
        {
            trie[trie[idx].e[s[0]-'A']].t++;
            return ;
        }
        else
            insert(trie[idx].e[s[0]-'A'],s+1,len);
    }
}

void struct_AC()
{
    int i,r,v,u;
    for(i=0; i<26; i++)
        if(trie[0].e[i]==-1)
            trie[0].e[i]=0;
    front=rear=0;
    for(i=0; i<26; i++)
        if(trie[0].e[i]>0)
        {
            trie[trie[0].e[i]].f=0;
            push(trie[0].e[i]);
        }
    while(rear>front)//struct f and t for each node
    {
        r=pop();
        for(i=0; i<26; i++)
            if(trie[r].e[i]>-1)
            {
                u=trie[r].e[i];
                v=trie[r].f;
                while(trie[v].e[i]==-1){
                    v=trie[v].f;
                }
                trie[u].f=trie[v].e[i];
                trie[u].t+=trie[trie[v].e[i]].t;
                push(u);
            }
    }
}


int main()
{
    int i,num;
    char s[25];
    cin>>N;
    SCRN
    ini();
    for(i=0; i<N; i++)
    {
        gets(s);
        insert(0,s,strlen(s));
    }
    struct_AC();
    return 0;
}