自动机

有啥要学的？ DFA/NFA 的记号：\((Q,\Sigma,\delta,q_0,F)\)。 NFA 到 DFA：子集构造（到 \(2^n\) 级别的构造：所有最后第 \(n\) 位为 \(1\) 的 01 串）。 \(\varepsilon-\)NFA 到 DFA：类似地进行子集构造，每次转移时 ......

一种很好写的 \(O(n\log ^2 n)\) 的做法和处理技巧，不需要会任何 border series 的知识，只需要会 SAM 和一些基础数据结构就行。 考虑 \(\text{MaxBorder}(l,r)\) 可以被写成即找到最大的 \(p \leq r - l\) 满足 \(S[l:l+ ......

对OI WIKI进行了抄写删减精炼 定义 字符串 \(s\) 的 SAM 是一个接受 \(s\) 的所有后缀的最小 DFA（确定性有限自动机或确定性有限状态自动机）。 SAM是一张有向无环图。节点称作状态，边称作转移 图存在一个源点\(t_0\)，称作初始状态（即下图红点），其他节点均可从\(t_0 ......

没写完后面补 什么是自动机 一般指确定有限状态自动机，所以AC自动机不是自动AC机 自动机是一个非常广泛使用的数学模型 自动机是一个对信号序列进行判定的模型 解释一下上面那句话 信号序列是指一串有顺序的信号例如字符串的从前到后每一个字符 判定是指对某一个命题给出真或者假的判断 对于自动机，一共存在3 ......

KMP 与 AC自动机 都是字符串匹配 KMP是单模匹配 ac自动机是多模匹配 KMP原理 例子 当我们匹配字符串A(长度为n)中是否有B(长度为m, m<n)的时候 比如: A ABCDABCDEF B ABCDE 一个朴素的思路是暴力, 复杂度当然是O(n * m) KMP就是一个优化的算法 K ......

目录写在前面结构构造复杂度证明模板题代码写在最后 写在前面 其实这东西学名叫 EER Tree，Palindromic Tree，直译是回文树，但本质上是一类有限状态自动机所以也可以叫 Palindromic Automaton，因为我很喜欢自动机所以以下都叫它回文自动机。 结构 类似后缀自动机的， ......

1. 哈希（Hashing）：哈希是一种将字符串转换为唯一标识符的技术，通常用于字符串的快速查找和比较。实现难度相对较低，但需要处理哈希冲突的问题。哈希在处理大量数据的查找和比较问题时非常实用。2. KMP（Knuth-Morris-Pratt）：KMP 是一种用于字符串匹配的算法，特别适用于查找子 ......

记录回文自动机的一些应用实例 ​ 题目主要来源 模板 ​ 跑\(PAM\)就是构建两棵字典树，字典树上（奇偶）根到不同节点都对应了一个原串中本质不同的回文串，同时维护了每个回文串对应的最长回文后缀。 ​ 这个模板定义节点\(0\)为偶根，节点\(1\)为奇根（有些板子可能反过来） \(next[i] ......

双数组字典树能在O(1)（1是模式串长度）时间内高速完成单串匹配，并且内存消耗可控，然而软肋在于多模式匹配。如果要匹配多个模式串，必须先实现前缀查询，然后频繁截取文本后缀才可多匹配。比如 ushers、shers、hers…这样一份文本要回退扫描多遍，性能较低。既然 AC 自动机的goto表本身就是 ......

一句话题解：AC自动机，在fail树上自顶向下预处理，以实现O(1)统计答案 Description: n个模式串{Sn}，1个文本串T。每次小B会选取T的一个子串（只要子串位置不相同则视作不同），对答案的贡献是该子串中含有的模式串的总数目。对于选取子串的所有方法，求总共的答案。 Solution: ......

解题思路： 对于每个询问串的查询可以改为以节点为后缀来统计有多少个查询串在里面然后来统计答案。拿下面这个例子来说： 3 1 a bb abb aabb 首先对查询串(n个串)构建AC自动机，对于每个字符串结尾位置的状态p设置sum[p] = 1, 同时插入的时候维护每个状态的长度len[p]。 我们 ......

from pixiv 有穷自动机 有穷自动机(finite state automata)是一个识别器，它对每个输入的字符做识别和判断，以确定其能到达的最终状态或状态集和路径，有穷自动机分为两类，即不确定的有穷自动机NFA和确定的有穷自动机DFA. 首先要重点区别一下DFA和NFA： DFA的初态是 ......

AC自动机与dp 前言： 本篇题解隶属于https://www.cnblogs.com/linghusama/p/17742870.html部分 首先一定要理解fail跳的原理，不然很难理解第二维为什么要设置。 首先给出大致的雏形，dp_i_j表示目前拼凑出长度为i的字符串，且ac自动机上的指针在j ......

AC自动机自学笔记 目录AC自动机自学笔记用途：定义：Tire字典树Kmp算法：ac自动机代码（基础版）：代码记忆方式：加强版分析：代码（加强版） 用途： 要学习之前肯定是要知道ac自动机是拿来干嘛的噻。 可以在一个字符串S中找到s1,s2,s3....的出现点以及出现次数。 定义： AC，当然不是 ......

OI 中的自动机指的是“有限状态自动机”，它是对一串信号进行处理的数学模型，一般由以下三部分构成： 字符集（\(\Sigma\)），能够输入进自动机的字符集合。 状态集合（\(Q\)) ，相当于有向图中的节点。 转移函数（\(\delta\)），相当于有向图中的边。 我们通过输入的信息在这个有向图中 ......

PAM 是一种高效存储字符串中所有回文子串的自动机，用于解决回文串相关问题。 虽然代码稍微长一点，但写起来比 manacher 容易很多，毕竟没有加了一堆字符再转回原串的若干上取整下取整问题。 前置知识 无。或许需要一些自动机相关的理论基础。 结构 & 定义 状态 我们用 PAM 上的一个节点来表示 ......

写在前面 本篇代码来源于yyb大佬的博客（指路） 加上了一些自己的理解，重写了代码注释，可能算转载plus罢。 代码思路 说到AC自动机，总会提起这个老生常谈的前置知识：Trie+KMP 事实上，它的代码也几乎就是这两者的组合形式。 主体部分： 建Trie树，求失配指针，查询 （即build，get ......

敏感词过滤在社区发帖、网站检索、短信发送等场景下是很常见的需求，尤其是在高并发场景下如何实现敏感词过滤，都对过滤算法提出了更高的性能要求，Ahocorasick算法能够实现毫秒级的万字过滤匹配，能够很好的满足各种场景下的敏感词过滤需求。 Aho-Corasick算法通过将模式串预处理为确定有限状态自 ......

题目传送门 CF1437G 好题 观察这道题，发现有关字串的题目，一般来说，这种题都要构建\(AC\)自动机，所以考虑构建。 构建之后，原来的所有 \(fail\) 是一个树形结构。 解法 \(1\): 考虑从询问入手，那么对于每一个询问，等价于就是查询每一个 \(Q_i\) 包含的后缀的最大值，再 ......

......

Smiling & Weeping 自从我们相遇的那一刻，你是我白天黑夜不落的星 题目链接：Problem - 2222 (hdu.edu.cn) 题目就是一道AC自动机模板 Talk is cheap , show me the code 1 #include<iostream> 2 #inclu ......

$Sam$ 复杂度和空间都成线性，但不能只开 $n$ $endpos$ 1，定义 $endpos$ 为每个子串出现的开头集合 2，定义 $Sam$ 每个节点为“状态”，则每个状态对应着一个或者多个 $endpos$ 相同的集合 后缀链接$link$ 1，连向当前子串后缀中非同一 $endpos$ 的 ......

cnblogs 怎么又炸了。只能先写在这里了。 为什么又可爱又强的 xxn 去年 9 月就会的科技樱雪喵现在还不会呢 /kel。 感觉 SAM 的教程已经被前人写烂了啊。那就写点个人学习过程中对 SAM 的理解。 参考资料：[KesdiaelKen-史上最通俗的后缀自动机详解](https://ww ......

## 相关概念 自动机理论中的重要定理：1、任何NFA接受的语言都可以被一个DFA接受。2、如果一个正则语言不是空语言，那么它具有两个不同的 minimal automata。3、任何正则语言都有一个“规约”自动机。 在 ==自动机理论== 中，语言的设计和识别是主要的研究目标，而 ==自然语言== ......

题目链接：[https://www.luogu.com.cn/problem/P2292](https://www.luogu.com.cn/problem/P2292) 题目大意： 给定 $n(\le 20)$ 个模式串 $s_i(|s_i| \le 20)$，有 $m(\le 50)$ 次询问， ......

题目链接：[https://www.luogu.com.cn/problem/P3808](https://www.luogu.com.cn/problem/P3808) AC自动机模板题。 示例程序： ```c++ #include using namespace std; const int m ......

### 前言 AC自动机（$Aho\ Corasick\ Atomaton$）有着一种 [$KMP$](https://www.cnblogs.com/pdpdzaa/p/17641166.html) 的思想，所以在学习之前建议先学一下 $KMP$。同时还需要了解一下 $Trie$ 树（建议去看一下 ......

[传送门](https://www.luogu.com.cn/problem/P5496) 我认为理解回文自动机需要图，以$abbaabba$为例，它的回文树是这样的：  令 ......

# [AC自动机](https://www.acwing.com/problem/content/description/1284/) 本质上是 KMP+Trie。 每个节点存储的 $ne$ 类似于 `KMP`，表示最长公共前后缀（前缀可以是从根出发的任意一条路径）。代码可以从 `KMP` 一一对应 ......

# 1. AC 自动机 ACAM ## 1.1. 介绍 AC 自动机用于解决多模式串匹配问题，例如求多个模式串在文本串中的出现次数。显著地，它的应用实际上非常广泛。 借助 KMP 的思想，我们对 Trie 树上的每个节点构造其**失配指针** $fail_i$，指向对于当前字符串的最长后缀（其他（前 ......