Back to Posts

AC自动机学习笔记

Posted in OI

预备知识:KMP和Tire树

  • KMP

    1.1 这是啥?

    ​ KMP可以以O(n+m)的复杂度解决两个字符串的匹配问题(一个模式串一个匹配串)

    1.2 核心思想:

    ​ 普通的字符串匹配显然是一个一个枚举,到一个失配的字符的时候,从头枚举,但是当第i失配的时候。

    ​ 前i-1是已经匹配了的,所以要借助匹配好的信息,通过next数组找到当前字符可能匹配到的模式字符的位置。

    1.3 具体实现:KMP

  • Tire树

    2.1 这是啥?

    ​ Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。

    ​ 典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。

    ​ 它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。

    2.2 核心思想:

    ​ Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

    它有3个基本性质:

    1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
    2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
    3. 每个节点的所有子节点包含的字符都不相同。
    

AC自动机的用处

与KMP相同的是都是用来匹配字符,但AC自动机可以用来匹配多个模式串。

PS:看到用处后个人口胡出的一些思路:

1、处理这个问题显然最简单的就是一个一个的匹配,时间显然不行。
2、考虑到优化问题:
	2.1 第一个优化思路是通过KMP算法得来的,考虑弄一个next数组,在这个Trie树的链上做出和KMP一样的操作。
	2.2 第二个优化的思路是通过Tire树的思想得来的,考虑有两个模式串,就最后一个字符的差别。
	    重新做一遍显然太浪费了,运用Tire树前缀的思想优化重复部分。

以上纯为没了解AC自动机前的口胡,dalao勿喷

本蒟蒻也就是通过上面两个SB的优化思路总结的预备知识

AC自动机

Read Next

BZOJ1179[APIO]Atm