Loading...

AC自动机 学习笔记

check评论:0 条 remove_red_eye浏览量:293 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-03-08

并不是自动ac机

AC自动机,可以用来解决多个模式串在一个文本串中匹配的问题,由于对于每一个模式串都跑一次$kmp$会很慢,所以将所有的模式串建成一个$trie$,然后用$kmp$的思想,在$trie$上构建$fail$指针并将无用的节点删去,就构成了一个$trie$图,然后在每个节点上记录当前单词答案,最后统计即可

构建$fail$指针的时候,用一个队列来扩展,现在扩展到哪个结点了,他的第$i$个子节点的$fail$就是他的$fail$的第$i$个子节点,即可

例题:洛谷P3808 AC自动机

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int vis[26],end,fail;
}ac[3000000];
char opt[1000010];
int cnt=0;
void ins()
{
    int l=strlen(opt),now=0;
    for(int i=0;i<l;i++)
    {
        int p=opt[i]-'a';
        if(ac[now].vis[p]==0)
        {
            ac[now].vis[p]=++cnt;
        }
        now=ac[now].vis[p];
    }
    ac[now].end++;
}
void getfail()
{
    queue<int> q;
    for(int i=0;i<26;i++)
    {
        if(ac[0].vis[i]!=0)
        {
            q.push(ac[0].vis[i]);
            ac[ac[0].vis[i]].fail=0;
        }
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            if(ac[u].vis[i]!=0)
            {
                ac[ac[u].vis[i]].fail=ac[ac[u].fail].vis[i];
                q.push(ac[u].vis[i]);
            }
            else
            {
                ac[u].vis[i]=ac[ac[u].fail].vis[i];
            }
        }
    }
}
int query()
{
    int ans=0;
    int l=strlen(opt),now=0;
    for(int i=0;i<l;i++)
    {
        now=ac[now].vis[opt[i]-'a'];
        for(int t=now;t!=0&&ac[t].end!=-1;t=ac[t].fail)
        {
            ans+=ac[t].end;
            ac[t].end=-1;
        }
    }
    return ans;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",opt);
        ins();
    }
    getfail();
    scanf("%s",opt);
    printf("%d",query());
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名