AC自动机小结-白红宇

AC自动机小结

阅读量：5318 次

发布时间：2019-06-14

本文共 790 字，大约阅读时间需要 2 分钟。

一. 模板

1 struct Trie 2 { 3     int sz, M[256]; 4     int next[MAXN][50], fail[MAXN], end[MAXN]; 5     int root, L, id // L为结点个数， id为单词个数。id可选择使用 6      7     int newnode() 8     { 9         for(int i = 0; i

Q;38 fail[root] = root;39 for(int i = 0; i

View Code

二. 题目类型

1.单纯的匹配：

（出现的单词种类数）

（出现的单词种类及其出现次数）

（需要解码）

（分可重叠和不可重叠统计）

2.字符串(不)含有单词的统计：

（长度为n且不含单词的字符串个数）

（长度小于等于n且不含单词的字符串个数）

（修改原串使其不含单词）

（需要大数）

3.字符串含有特定个单词的统计：

4.字符串含有所有type1单词且不含type2单词的统计：

5.字符串长度小于等于n且价值最大的统计：

（需要输出字符串）

三. 对AC自动机的一些浅薄的理解

1.AC自动机的结构特点：

1）前缀性：由于AC自动机是以字典树为基础的，所以插入自动机里的单词，存在前缀重叠。

2）后缀性：这是由fail[]数组决定的，当当前位置匹配失败时，匹配的指针就自动跳到与当前字符串后缀匹配最大的那个状态。

2.AC自动机中状态之间的关系：

AC自动机中，每个结点都代表着一个状态。他们之间的关系构成了一张有向图。因此，当建立好自动机之后，就可以把状态之间的关系抽出来构成一张图，然后再根据这张图进行数据统计，如路径数、最短路径之类的。

转载于:https://www.cnblogs.com/DOLFAMINGO/p/8462612.html

你可能感兴趣的文章