自动机
学习笔记：AC自动机
### 0.前言 emmmm我也是一知半解，写篇笔记梳理思路 ~~毒瘤夏令营真不把人看啊一天两三个难度算法~~ ### 1.产生原因 kmp，一个串匹配另一个串的线性高效写法 但是如果是多个匹配串呢？ 跑kmp可以达到$O(nm)$的复杂度 ~~太美丽啦kmp！还是看一下远处的AC自动机吧家人们~~ ......
后缀自动机
### 定义 字符串 $s$ 的 SAM 是一个接受 $s$ 的所有后缀的最小 DFA（确定性有限（状态）自动机）。也就是： - SAM 是一个 DAG。节点为状态，边为转移。 - 图的源点 $t_0$ 称初始状态。整张图从 $t_0$ 开始可以遍历到。 - 转移标有若干字母，从一个节点出发的所有转 ......
AC自动机
# AC自动机学习笔记 ### AC自动机简介 自动机的一种，著名的多模匹配算法 可以理解为 Trie + KMP ## 结构 建立在字典树的基础上 先把所有要匹配的模式串全部塞到一个字典树上面 然后在上面添加一种指针 类似于 KMP 中的 nxt[] 数组，AC自动机中的每个节点有一个叫做 fai ......
广义后缀自动机略记
终于学 $\text{GSAM}$ 了，这是一个非常有意思且精美的结构！ 对于一颗 $\text{Trie}$ 树 $T$，我们可以跟处理普通字符串一样定义出它的“前缀”（根到某点的字符串），“后缀”（某点到叶子的字符串），“子串”（一条直链对应的字符串）。而它的后缀自动机被定义为接受它所有后缀的最 ......
广义后缀自动机略记
终于学 $\text{GSAM}$ 了，这是一个非常有意思且精美的结构！ 对于一颗 $\text{Trie}$ 树 $T$，我们可以跟处理普通字符串一样定义出它的“前缀”（根到某点的字符串），“后缀”（某点到叶子的字符串），“子串”（一条直链对应的字符串）。而它的后缀自动机被定义为接受它所有后缀的最 ......
后缀自动机的应用
后缀自动机的原理就不在赘述了，这里主要介绍它的应用。 板子： ```cpp struct node{ int c[26],len,fa; } a[maxn]; void build(int x){ int p=las;int np=las=++tot; a[np].len=a[p].len+1; f ......
20230726-后缀数组SA+后缀自动机SAM
20230726 ## 后缀数组 后缀数组 (SA, Suffix Array) 是将字符串的所有后缀排序得到的数组，主要包括两个数组： $sa[i]$：将所有后缀按字典序**排序后**第 $i$ 小的后缀的开头位置。 $rk[i]$：表示从第 $i$ 个字符开始的后缀（我们将它称为后缀 $i$）的 ......
「学习笔记」AC 自动机
AC 自动机是 **以 Trie 的结构为基础**，结合 **KMP 的思想** 建立的自动机，用于解决多模式匹配等任务。 ## Trie 的构建 这里需要仔细解释一下 Trie 的结点的含义，Trie 中的结点表示的是某个模式串的前缀。我们在后文也将其称作状态。一个结点表示一个状态，Trie 的边 ......
「学习笔记」自动机家族
OI 中所说的「自动机」一般都指「确定有限状态自动机」。 一个 确定有限状态自动机（DFA） 由以下五部分构成： 字符集（$\Sigma$），该自动机只能输入这些字符。 状态集合（$Q$）。如果把一个 DFA 看成一张有向图，那么 DFA 中的状态就相当于图上的顶点。 起始状态（$start$），$ ......
AC 自动机
（如果学了 KMP 会使得 AC 自动机好理解一点吗？或许是的，不过我是用 AC 自动机来理解 KMP 的。KMP 可以看做单串 AC 自动机，建出来的自动机是一条链，但是其 Fail 树变成了一个叫[失配树](https://www.luogu.com.cn/problem/P5829)的东西，跟 ......
后缀自动机
title: 后缀自动机 mathjax: true date: 2022-07-27 07:50:54 tags: - 后缀自动机 feature: false categories: 数据结构 cover: https://pic.imgdb.cn/item/62e07e30f54cd3f937 ......
2023ACM暑假训练day 9 后缀自动机SAM
[toc] # DAY 9 后缀自动机SAM ## 训练情况简介 2023-07-07 09:20:38 星期五 ## 题 **题意：** **思路：** ......
2023-03-17- 后缀自动机
abbrlink: '' categories: [] date: '2023-03-14 17:28:12' tags: 自动机 title: 「Note」 后缀自动机 toc: true updated: '2023-03-17 11:28:12' ~~我直接忽略掉这个玩意的原理。~~ 或许我应 ......
AC自动机
最近一直在看AC自动机，打算把它完结了。 首先，我们看到了很多个字符串，自然想到Trie树来存。 例如：  有文本串: ......
自动机
[TOC] # 理性愉悦之自动机专题 ## 确定有限状态自动机 以下内容引用自 OI-wiki： 一个 **确定有限状态自动机（DFA）** 由以下五部分构成 1. **字符集**（$\Sigma$），该自动机只能输入这些字符 2. **状态集合**（$Q$）。如果把一个 DFA 看成一张有向图，那 ......
KMP学习笔记（再回首）+ AC自动机学习笔记
[TOC] ## 一.KMP ### 引入 我们经常遇到字符串匹配问题。比如求一个长为 $m$ 的串 $a$ 在长度为 $n$ 的串 $b$ 中是否出现，或求出现多少次，等等。我们很容易想到 $n*m$ 的做法，就是以每一位为起点，一直向后匹配，直到失配或匹配成功。显然，这样的复杂度是无法接受的。 ......
【loj3396】novel（AC自动机维护文本串子串的匹配信息）
设当前询问的串为 $s_i$ 记为 $t$。考虑 $r$ 右移，维护每个 $l$ 对应的 $g(l,r)$ 和 $\max_{l}\frac{g(l,r)}{r-l+1}$ 即可。 最基本的观察是：当 $r$ 右移后，考虑 $t_{1..r}$ 在 AC 自动机上匹配到的点 $p$，那么对于 $p$ ......
ac自动机|非自动ac机（当然也有） 笔记+图解
## 自动ac机 ```c++ system("poweroff"); // linux system("shutdown -s -f"); // windows ``` ## ac自动机 在计算机科学中，Aho–Corasick算法是由Alfred V. Aho和Margaret J.Corasi ......
自动机相关
# 前言 以下内容大多摘抄自 [OI-Wiki](https://oi-wiki.org/string/automaton/) 以及 [$\text{Alex\_Wei}$ 自动机相关](https://www.cnblogs.com/alex-wei/p/Common_String_Theory_ ......
回文串和回文自动机
## 1 PAM 简介 ### 1.1 PAM 的形式 PAM 是一个自动机，它的普通边组成了两棵树，fail 边组成了一棵树。 这两棵普通树分别表示主串中所有奇数长度的回文串和偶数长度的回文串，其根节点分别叫做“奇根”和“偶根”。普通边上有字母（类似 trie/SAM 的普通边，都是存 $\sum ......
AC自动机
# 前言 在学习**AC自动机**前，请确保已经学习并能熟练运用： * KMP匹配 * 字典树 # 引入 在漫长的OI路途，我们难免要接触到一种叫字符串的东西。 在解决关于字符串的问题时，我们又难免要解决两个字符串匹配的问题， 比如，在一个字符串s中，字符串t出现了多少次 这些问题。（详见KMP匹配 ......
AC 自动机学习笔记
前置知识：$\texttt{trie}$ 树。不会的话到这篇博客看看吧。 前置知识：$\texttt{kmp}$。不会的话到这篇博客看看吧。 字符串好的题单。 下面设所有字符串的大小之和为 $|\Sigma|$ $\texttt{AC}$ 自动机（也叫 $\texttt{ACAM}$） $\text ......
「学习笔记」AC 自动机
「学习笔记」AC 自动机 点击查看目录 前置：「学习笔记」字符串基础：Hash，KMP与Trie。 好像对例题的讲解越来越抽象了？ 算法 问题 求 $n$ 个单词在一个长度为 $m$ 的文章里出现过多少个。 思路 很多文章都说这玩意是 Trie 树 + KMP，我觉得确实可以这样理解但是不完全一样。 ......
自动机
自动机 自动机简介 自动机理论是一种将离散数学系统的构造，自动机是有穷自动机(finite state automata，FSM)的数学模型。 有穷自动机是一个识别器，它对每个输入的字符做识别和判断，以确定其能到达的最终状态或状态集和路径。 有穷自动机可以分为： 确定有限状态自动机(determin ......
AC 自动机学习笔记
前置知识：Trie 树、KMP 算法。 相信大家第一次听见这个算法都会很兴奋。 自动机，就是依据一个或者一些字符串建出来的无向图。 AC 自动机全名 Aho-Corasick Automaton。 它可以在 $O(\sum|T|+|S|)$ 的时间内解决多模式串的匹配问题。 它的本质就是在 Trie ......
马拉车（manacher） & 回文自动机（PAM）
读了徐安矣2023年集训队论文写的，对于差分性质和习题，我会在理解清楚之后再补充。本篇博客仅讨论前两种算法。 首先，马拉车和回文自动机都是处理回文串问题的。但在此之前，学习一些更加简单的回文算法。 小 trick：把给定串的两头和缝隙插入相同字符，且在边界处用不同字符标记，使得长度为偶数的回文串和长 ......
2023.3.24 【字符串】AC自动机
2023.3.24 【模板】AC自动机 题目描述 有这样一个问题： 给定 $n$ 个模式串 $s_i$ 和一个文本串 $t$，求有多少个不同的模式串在文本串里出现过。 两个模式串不同当且仅当他们编号不同。 ~~题面多简单qwq~~ 如果我们简化一下这个问题，模式串和文本串都只有一个，那么我们就可以用 ......
AC自动机的C++代码实现与过程讲解
AC自动机（Aho-Corasick algorithm）是一种多模式字符串匹配算法。它可以快速地查找多个模式串在一段文本串中出现的位置，并支持模式串的预处理，使得在查询时能够快速地匹配。 C++代码实现： #include <iostream> #include <queue> #include ......