2020-2021:teams:no_morning_training:shaco:知识点:数据结构:ac自动机
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:shaco:知识点:数据结构:ac自动机 [2020/07/16 18:23] shaco |
2020-2021:teams:no_morning_training:shaco:知识点:数据结构:ac自动机 [2020/07/26 19:10] (当前版本) shaco |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ====== 简述 ====== | ====== 简述 ====== | ||
| AC自动机可以说是KMP的进阶版，支持多个模式串在目标串中的查询。\\ | AC自动机可以说是KMP的进阶版，支持多个模式串在目标串中的查询。\\ | ||
| - | 复杂度为$O((N+M)\times L)$。 | + | 复杂度为$O((N+M)\times L)$。\\ |
| ====== 思路 ====== | ====== 思路 ====== | ||
| 首先对模式串进行trie树的构建。\\ | 首先对模式串进行trie树的构建。\\ | ||
| - | 接着引入$\text{fail}$的概念：对于trie树的每一个结点都有一个fail值，fail对应了另一个树上的结点，从root到fail的字符串是从root到该结点的字符串的最大后缀。 类似于$/text{KMP}$中的$/text{Next}$数组。 | + | 接着引入$\text{fail}$的概念：对于trie树的每一个结点都有一个fail值，fail对应了另一个树上的结点，从root到fail的字符串是从root到该结点的字符串的最大后缀。 类似于$\text{KMP}$中的$\text{Next}$数组。 |
| 匹配过程中，若对一个结点匹配，则对其fail、fail'sfail....均匹配；若对一个结点失配，则应来到其父结点的fail再进行匹配。 | 匹配过程中，若对一个结点匹配，则对其fail、fail'sfail....均匹配；若对一个结点失配，则应来到其父结点的fail再进行匹配。 | ||
| ====== 操作 ====== | ====== 操作 ====== | ||
2020-2021/teams/no_morning_training/shaco/知识点/数据结构/ac自动机.1594895013.txt.gz · 最后更改: 2020/07/16 18:23 由 shaco
