自动机

瞎扯，不做教程。 回文自动机是接受串 $s$ 所有本质不同回文子串的类自动机结构。 考察该类自动机结构的转移边上字符的含义，因为回文串是回文的，所以从 $s$ 转移到 $t$ 应该在 $s$ 所代表的字符串两边均加上转移边上的字符 $c$。 这样就会有一个问题：考虑每次走转移边字符串长度都增加 $2 ......

由于本人时间原因，此处只为一个SAM的总结，讨论SAM的基本操作以及性质，详细证明 如要详细学习请查询luogu题解。 算法原理 SAM中每一个节点代表所有结束位置（endpos）相同的串的集合。 每个节点有：1.后缀链接link（到endpos包含它且maxlen最长的那个点，且是为当前点的后缀的 ......

概念 回文自动机，PAM，又叫回文树。 用于处理和回文子串有关的问题，和 SAM 有一些类似的地方。 构造 首先 PAM 上的每个结点代表原串的一个回文子串。 根据神秘结论，原串本质不同的回文子串至多有 $n$ 个，也就是 PAM 的点数至多是 $n + 2$，边数至多是 $n$. 考虑到回文串的奇 ......

后缀自动机是通过一个DAG图来存储的，使空间更小，后缀自动机中最关键的一项技术叫做后缀链。 1.建立SAM void insert(int c){ newNode(t[last].len+1); int p=last,cur=sz; while(p!=-1&&!t[p].son[c])t[p].so ......

P5357 #include <bits/stdc++.h> #define int long long #define N 200005 using namespace std; int n, cnt[N] = {0}; string s[N], t; map<string, int> apr; ......

AC自动机的核心思想： **如果当前模式串匹配成功部分的后缀与其他某个模式串的前缀一致，则如果在下一次匹配失败时，直接匹配那个模式串的与当前模式串的后缀不同部分。** 举例： 模式串1 `abcd`，模式串2 `bcf`，模式串3 `e`。 ......

用于解决多模式串匹配相关问题。实际上就是 KMP 在多串的扩展。 首先建出字符串的 trie 树，然后 AC 自动机只是在 trie 树上加了一些边。 只需要记住：儿子的 fail 就是 fail 的儿子，不存在的儿子直接是 fail 的儿子，然后 bfs 即可。 然后解决的问题类似于给定若干模式串 ......

AC自动机 前置知识： 字典树：可以参考我的另一篇文章 算法学习笔记(15): Trie（字典树） ~~KMP~~：可以参考 KMP - Ricky2007，但是不理解KMP算法并不会对这个算法的理解产生影响。 使用场景 AC自动机是一种著名的多模式匹配算法。 可以完成类似于KMP算法的工作，但是由 ......

后缀自动机 自动机 首先什么是自动机 我们大多用的是$DFA$,也就是有限状态自动机 整个自动机是由一些边和点组成的,边上的权为字符 简单理解就是输入一个字符串如果是我们想要接受的，那这个字符串就会按顺序遍历图,并最后会在终止节点停下,是为接受 当然,也有一些字符串无法被接受,比如AC自动机就是接受 ......

传送门 题目大意 ** 有T组测试数据，对于每组测试时局有一个n和m，n表示初始拥有的字符串数量，m表示操作数量。紧接着输入n个字符串，再读入m行操作，每行以x str的形式给出，如果x为1则是往所拥有的字符串内插入str，若x为2则是查询当前字符串包括了多少完整的字符串（重复出现也算）。** ** ......