AC自动机总结

FREEH · 2018-03-08 14:23:20 · 题解

【算法目标】

• 给出多个字典单词和一个匹配字符串，求出匹配字符串中存在多少个字典单词。

【算法思路】

• 一、假如我们不会AC自动机，我们会怎么做？

  • 对于给出的每个字典单词，将它加入一棵Trie树里，然后把匹配字符串中的每一个单词在Trie树中跑一遍，然后统计就行了。但是这样分解匹配字符串时间复杂度很高。

• 二、AC自动机运用了KMP的思想

  • KMP中有一个next数组，失配时用于跳跃。AC自动机也运用了这个思想。
  • AC自动机处理的是字典单词。它也有一个失配数组fail，表示：以当前字符串为后缀的最长的字符串。fail指针的用途是当匹配字符串在Trie树上跑时，得以用fail指针不断地跳统计数量，优化时间。

• 三、fail指针的构造

  • 先把字典单词加入Trie树。然后用bfs一层层扫描Trie树。明显的，根节点的子节点的fail如果当前节点有子节点，那么子节点的fail节点就是当前节点的fail节点的子节点。
  • 有一个剪枝，就是如果当前节点没有子节点时，就把当前节点的子节点指向当前节点的fail节点的子节点。

• 四、统计。

  • 把匹配字符串在AC自动机上像Trie树一样跑，只是跑到的每一个节点都要不断地顺着fail指针走一次，并且统计总数。

【参考程序】

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

char st[1000005],p[1000005];
struct TRIE{
    int son[27];
    int val;
}trie[1000005];
int fail[1000005];
int L;

void Fill_in(char *st,int rank)
{
    int len=strlen(st),u=0;
    for (int i=0;i<len;i++)
    {
        int v=st[i]-'a';
        if (!trie[u].son[v])
            trie[u].son[v]=++L;
        u=trie[u].son[v];
    }
    trie[u].val++;
}
void Build()
{
    queue <int> q;
    for (int i=0;i<26;i++)
        if (trie[0].son[i])
        {
            q.push(trie[0].son[i]);
            fail[trie[0].son[i]]=0;
        }
    while (!q.empty())
    {
        int now=q.front();q.pop();
        for (int i=0;i<26;i++)
            if (trie[now].son[i])
            {
                fail[trie[now].son[i]]=trie[fail[now]].son[i];
                q.push(trie[now].son[i]);
            }else
            trie[now].son[i]=trie[fail[now]].son[i];
    }
}
int Check(char *st)
{
    int len=strlen(st),u=0,ans=0;
    for (int i=0;i<len;i++)
    {
        u=trie[u].son[st[i]-'a'];
        for (int h=u;h&&~trie[h].val;h=fail[h])
        {
            ans+=trie[h].val;
            trie[h].val=-1;
        }
    }
    return ans;
}
int main()
{
    int T,n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%s",st);
        Fill_in(st,i);
    }
    Build();
    scanf("%s",p);
    printf("%d",Check(p));
    return 0;
}