首页 > 其他分享 >AC自动机

AC自动机

时间:2023-08-05 19:45:10浏览次数:43  
标签:AC int tr str fail 自动机

AC自动机学习笔记

AC自动机简介

自动机的一种,著名的多模匹配算法

可以理解为 Trie + KMP

结构

建立在字典树的基础上

先把所有要匹配的模式串全部塞到一个字典树上面

然后在上面添加一种指针

类似于 KMP 中的 nxt[] 数组,AC自动机中的每个节点有一个叫做 fail 的指针(失配指针)

与 KMP 类似,

fail 表示最长的相等前后缀,只不过不是一个字符串上面考虑,而是在整棵字典树上面考虑

fail就是从后缀的结尾指向前缀的结尾

举个例子

这张图是

she shr say her he

这五个字符串构建出来的AC自动机 红色的是 fail

来看一眼左下角的那个点

他表示的字符串是 she

有一个后缀 he 正好是 her 的前缀,所以这个点就要指向 her 的‘e’

其余同理

(根节点的 fail 指向自己)

构建过程

求 fail[i] 需要用到比 i 深度小的所有点

因此使用 深度优先搜索

当前考虑到了节点 u 他的父亲是 p 通过字符 c 转移而来

即 \(tr[p][c]=u\)

如果 tr[fail[p],c] 存在 则让 u 的 fail 指针指向 tr[fail[p],c]

否则一直往上跳(tr[fial[fail[p]],c],tr[fail[fail[fail[p]]],c], ...)实在找不到存在的就到根节点为止

代码
void build()
{
    for(int i=0;i<26;i++)
        if(tr[0][i])
            q.push(tr[0][i]);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            int v=tr[u][i];
            if(!v) tr[u][i]=tr[nxt[u]][i];
            else
            {
                nxt[v]=tr[nxt[u]][i];
                q.push(v);
            }
        }
    }
}

这里代码跟思路有点小不一样是因为加了个优化

变成了trie图

原本要一直往上跳 这回路径压缩

直接一跳到底

板子

例题链接:

AcWing 1282.

Code:

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

const int N=1e4+5,M=1e6+5,S=55;

int tr[N*S][26],cnt[N*S],idx;
queue<int> q;
string str;
int nxt[N*S];
int n;

void insert()
{
    int u=0;
    for(int i=0;str[i];i++)
    {
        int v=str[i]-'a';
        if(!tr[u][v])
            tr[u][v]=++idx;
        u=tr[u][v];
    }
    cnt[u]++;
}

void build()
{
    for(int i=0;i<26;i++)
        if(tr[0][i])
            q.push(tr[0][i]);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            int v=tr[u][i];
            if(!v) tr[u][i]=tr[nxt[u]][i];
            else
            {
                nxt[v]=tr[nxt[u]][i];
                q.push(v);
            }
        }
    }
}


int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(tr,0,sizeof(tr));
        memset(cnt,0,sizeof(cnt));
        memset(nxt,0,sizeof(nxt));
        idx=0;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>str;
            insert();
        }
        build();
        cin>>str;
        int ans=0;
        for(int i=0,j=0;str[i];i++)
        {
            int t=str[i]-'a';
            j=tr[j][t];
            int p=j;
            while(p)
            {
                ans+=cnt[p];
                cnt[p]=0;
                p=nxt[p];
            }
        }
        cout<<ans<<endl;
    }

    return 0;
}

明人不说暗话,其实AC自动机还有点没搞明白

需要再钻研

赶紧接着学习去了

钻研透彻了就更新修改一下

byebye

参考:AcWing算法提高课 OI Wiki

标签:AC,int,tr,str,fail,自动机
From: https://www.cnblogs.com/Orange-Star/p/16609162.html

相关文章

  • Vanya and Brackets 题解
    题目传送门一道枚举题。枚举左括号和右括号的位置括号,为了答案最优,左括号只能在开头或者*的右边。右括号只能在末尾或者*的左边。每一次枚举都计算一下这个加了括号后表达式的值,最后取最大值即可。Code#include<bits/stdc++.h>#definelllonglong#defineINF1e9usi......
  • 4 Diac中E_CYCLE模块源码分析
    E_CYCLE的源码分析一E_CYCLE的功能输入事件接口:START、STOP,输出事件接口EO数据输入接口:DTSTART是开启定时事件,STOP结束定时事件,EO是时间到了触发的事件,DT是配置时间间隔参数,数据类型为字符串类型。举例:DT输入T#10MS,则10MS触发一次EO事件   二源码分析该源码主要......
  • .Net Core ActionFilter
    目录作用实现IActionFilterIAsyncActionFilterActionFilterAttributeDemoCustomAsyncActionFilter.csTestFilterController.cs如何在Actionfilter使用日志Action.csCustomAsyncActionFilter.cs全局注册Program.cs作用在请求AuthorizeFilter->ResourceFilter->ActionFilt......
  • .git泄露利用脚本工具githack使用
    前言首先我们要明白git(一种分布式版本管理工具),它适用于我们多人协作开发,我们每个人对开发项目进行了修改git都会记录并产生快照也就是我们所谓的版本,我们可以很方便的查看甚至是回溯到我们之前的版本(也许我们在开发过程中会出现许多的不可控事故)但前提是我们不能删除.git文......
  • Practice on Codeforces and Atcoder in August
    EducationalCodeforcesRound151A~ECodeforcesRound#879Div.2CodeforcesRound#882Div.2CodeforcesRound#873Div.2......
  • Android开发 Jetpack Compose 与xml的混合开发AndroidView
    前言  JetpackCompose虽然已经逐渐完善,但是其实还是有很多地方未满足需求。比如播放视频、相机预览等等依然需要原来的View。所以目前阶段JetpackCompose与xml的混合开发非常重要。  官方文档地址:https://developer.android.google.cn/jetpack/compose/migrate/interopera......
  • 无涯教程-Perl - foreach 语句函数
    foreach循环遍历列表值,并将控制变量(var)依次设置为列表的每个元素-foreach-语法Perl编程语言中的foreach循环的语法是-foreachvar(list){...}foreach-流程图foreach-示例#!/usr/local/bin/perl@list=(2,20,30,40,50);#foreachloopexecutionf......
  • ERROR 1045 (28000): Access denied for user 'root'@'localhost' (using password: Y
    mysql登录提示vim/etc/my.conf增加skip-grant-tables问题分析https://blog.csdn.net/ibsfn/article/details/88963040......
  • CleanMyMac真的有必要买吗 2023年最新CleanMyMac和腾讯柠檬详细解析
    在如今的电脑使用过程中,保持电脑干净整洁是一项重要的任务。而随着Mac电脑越来越受欢迎,Mac电脑清理软件也愈发流行。在众多的Mac电脑清理软件中,CleanMyMac是一款备受好评的软件。但是,很多人还在犹豫CleanMyMac有必要买吗?同时,也有人想知道CleanMyMac和腾讯柠檬哪个好。接下来,我们将......
  • macbook怎么卸载软件?2023年最新全新解析macbook电脑怎样删除软件
    macbook怎么卸载软件?2023年最新全新解析macbook电脑怎样删除软件。关于Mac笔记本如何卸载软件_Mac笔记本卸载软件的四种方法的知识大家了解吗?以下就是小编整理的关于Mac笔记本如何卸载软件_Mac笔记本卸载软件的四种方法的介绍,希望可以给到大家一些参考,一起来了解下吧!Mac笔记本与Win......