AC自动机

字典树（数组实现）

http://www.cnblogs.com/TheRoadToTheGold/p/6290732.html

int trie[500005][26];//编号为i的节点的第j个孩子是编号为k的节点
int num[500005];//每个编号被访问的次数
int tot=1;//第一种编号
void Insert(char zs[])
{
    int len=strlen(zs);
    int pos=0;
    for(int i=0;i<len;i++)
    {
        int id=zs[i]-'a';//第二种编号
        if(!trie[pos][id])//如果对应字符还没有值
            trie[pos][id]=tot++;
        pos=trie[pos][id];//继续往下走
        num[pos]++;
    }
}
int Find(char zs[])
{
    int len=strlen(zs);
    int pos=0;
    for(int i=0;i<len;i++)
    {
        int id=zs[i]-'a';
        if(!trie[pos][id])
            return 0;
        pos=trie[pos][id];
    }
    return num[pos];
}
int main()
{
    char zs[15];
    memset(trie,0,sizeof(trie));
    memset(num,0,sizeof(num));
    while(gets(zs))
    {
        if(strcmp(zs,"\0")==0)break;
        Insert(zs);
    }
    while(gets(zs))
        printf("%d\n",Find(zs));
    return 0;
}

参考博客：

https://subetter.com/algorithms-and-mathematics/aho-corasick-algorithm.html

http://blog.csdn.net/baidu_30541191/article/details/47447175

步骤：

现给定 3 个单词 {“china”, “hit”, “use”}，再给定一段文本 “chitchat”，求有多少个单词出现在文本中。

1.根据单词 {“china”, “hit”, “use”} 建立字典树。

2.根据所给文本 “chitchat” 依次匹配，图中所示 “chi” 为匹配成功的字符串。

3.当匹配到第四个字符时，“t”和 “n” 匹配失败。

4.我们此时是知道已匹配成功的字符串的，即 “chi”。

AC 算法的核心就是在所有给定的单词中，找到这样的一个单词，使其与已匹配成功字符串的相同前后缀最长，利用这个最长的相同前后缀实现搜索跳转。如上图，单词 “hit” 与已匹配成功字符串 “chi” 的最长相同前后缀为 “hi”，因此下一步从单词“hit” 的“t”开始搜索。

5.此时 “t” 是匹配的，在文本 “chitchat” 中找到一个单词“hit”。

其实到这里，AC 算法的思想已经基本呈现在大家面前了。剩下的问题就是如何解决第（3）步所述的 “核心”。

创建失配指针：

在每个结点里设置一个指针（我们称之为 fail 指针），指向跳转的位置。

对于跳转位置的选择，基于以下两点：

对于根结点的所有儿子结点，它们的fail指针指向根结点；
对于其它结点，不妨设该结点上的字符为ch，沿着它的父亲结点的fail指针走，直到走到一个结点，它的儿子中也有字符为ch的结点，然后把该结点的fail指针指向那个字符为ch的结点。如果一直走到了根结点都没找到，那就把fail指针指向根结点。

模板：

int cnt,ans;
char a[1000010];
struct node
{
    int son[26];
    int fail;
    int num;
}nd[1000010];
void Insert()
{
    int len=strlen(a);
    int cur=0;
    for(int i=0;i<len;i++)
    {
        if(!nd[cur].son[a[i]-'a'])
            nd[cur].son[a[i]-'a']=++cnt;
        cur=nd[cur].son[a[i]-'a'];
    }
    nd[cur].num++;
}
void build_fail()
{
    queue<int>q;
    for(int i=0;i<26;i++)
    {
        nd[nd[0].son[i]].fail=0;
        if(nd[0].son[i])
            q.push(nd[0].son[i]);
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            if(nd[u].son[i])
            {
                nd[nd[u].son[i]].fail=nd[nd[u].fail].son[i];
                q.push(nd[u].son[i]);
            }
            else
                nd[u].son[i]=nd[nd[u].fail].son[i];
        }
    }
}
void query()
{
    int len=strlen(a);
    int cur=0;
    for(int i=0;i<len;i++)
    {
        cur=nd[cur].son[a[i]-'a'];
        for(int j=cur;j!=0&&nd[j].num!=-1;j=nd[j].fail)
        {
            ans+=nd[j].num;
            nd[j].num=-1;
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    cnt=0;
    nd[0].fail=0;
    while(n--)
    {
        scanf("%s",a);
        Insert();
    }
    build_fail();
    scanf("%s",a);
    ans=0;
    query();
    printf("%d\n",ans);
    return 0;
}