欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

模板总结——AC自动机

程序员文章站 2024-01-29 15:56:52
...

路径字符串

在Trie树中,某个结点的路径字符串是指从Trie的根结点到该结点的路劲上的边上的字符连起来形成的字符串。

后缀结点

一个结点x的后缀结点为非x结点y,当y的路径字符串为x的路径字符串的所有后缀中出现在字典树中(是字典的一个单词)最长的一个。

AC自动机

任务:
假设有多个模式串s1,s2,…,su,需要确定主串S中是否包含其中任意一个模式串。

解决:
通过在Trie树上添加一些额外的边组成,其核心部分是后缀结点的构建。

算法流程

(1)根据所有的模式串建立起Trie树
(2)从树根向下依此(BFS)计算每一个结点的后缀结点
(3)主串与求出后缀结点的Trie树进行匹配

根的直接子结点的后缀结点为根。对Trie树BFS,每个结点的后缀结点都由它的父节点的后缀结点决定。求出Trie树中所有存在的结点的后缀结点并入队列,不存在的结点存放其父节点的后缀结点。

void build()
{
    queue<int> que;
    for(int i=0;i<MAXC;i++)
    {
        if(child[0][i]==-1)
            child[0][i]=0;//不存在的根的直接子结点的编号改为根
        else
            que.push(child[0][i]);
    }
    while(!que.empty()) //BFS
    {
        int now=que.front();que.pop();
        int nxt=fail[now];//now的后缀结点
        for(int i=0;i<MAXC;i++)
        {
            int &c=child[now][i];//子结点
            if(c==-1)
                c=child[nxt][i];
            else
            {
                fail[c]=child[nxt][i];//当前结点的后缀结点由父节点的后缀结点决定
                que.push(c);
            }
        }
    }
}

枚举主串的每一个字符,找到其在Trie树对应的结点,沿着后缀结点一直走到根结点

int solve(char *s)
{
    int ans=0,p=0,len=strlen(s+1);
    for(int i=1;i<=len;i++)
    {
        p=child[p][s[i]-'a'];
        int tmp=p;
        while(tmp)
        {
            ans+=sta[tmp];
            sta[tmp]=0;
            tmp=fail[tmp];
        }
    }
}

模板

int child[maxn][MAXC];//Trie树
int fail[maxn];//后缀结点
int sta[maxn];//结点的附加信息
int tot;//结点的编号

void init()
{
    tot=0;
    memset(child,-1,sizeof(child));
    memset(fail,0,sizeof(fail));
    memset(sta,0,sizeof(sta));
}
void insert(char *s)//Trie
{
    int p=0,len=strlen(s+1);
    for(int i=1;i<=len;i++)
    {
        int v=s[i]-'a';
        if(child[p][v]==-1)
            child[p][v]=++tot;
        p=child[p][v];
    }
    sta[p]++;
}
void build()
{
    queue<int> que;
    for(int i=0;i<MAXC;i++)
    {
        if(child[0][i]==-1)
            child[0][i]=0;//不存在的根的直接子结点的编号改为根
        else
            que.push(child[0][i]);
    }
    while(!que.empty()) //BFS
    {
        int now=que.front();que.pop();
        int nxt=fail[now];//now的后缀结点
        for(int i=0;i<MAXC;i++)
        {
            int &c=child[now][i];//子结点
            if(c==-1)
                c=child[nxt][i];
            else
            {
                fail[c]=child[nxt][i];//当前结点的后缀结点由父节点的后缀结点决定
                que.push(c);
            }
        }
    }
}
int solve(char *s)
{
    int ans=0,p=0,len=strlen(s+1);
    for(int i=1;i<=len;i++)
    {
        p=child[p][s[i]-'a'];
        int tmp=p;
        while(tmp)
        {
            ans+=sta[tmp];
            sta[tmp]=0;
            tmp=fail[tmp];
        }
    }
}

下面就开始刷题了…
[kuangbin带你飞]专题十七 AC自动机