后缀自动机（单词的有向无环图）简介

在我们学习后缀自动机之前，一定要先了解什么是自动机？自动机（确定有限状态自动机）是由一个非空有限状态的集合Q、一个输入字母表 Σ（非空有限字符的集合）、一个转移函数（单值映射）、一个开始状态、一个接受状态（终结状态）的集合所组成的5-元组。

历史上，Blumer等人于1983年首次提出了后缀自动机的线性规模，然后在1985-1986年，人们提出了首个线性时间内构建后缀自动机的算法（Crochemore，Blumer等）。在文末链接处查看更多细节。

后缀自动机在英文中被称作“suffix automaton”（复数形式：suffix automata），单词的有向无环图——"direcged acyclic word graph"（简写为“DAWG”）。

而后缀自动机（单词的有向无环图）是一种强有力的数据结构，让你能够解决许多字符串问题。

例如，使用后缀自动机可以在某一字符串中搜索另一字符串的所有出现位置，或者计算不同子串的个数——这都能在线性时间内解决。

直觉上，后缀自动机可以被理解为所有子串的简明信息。一个重要的事实是，后缀自动机以压缩后的形式包含了一个长度为n的字符串的所有信息，仅需要O(n)的空间。并且，它能在O(n)时间内被构造（如果我们将字母表的大小k视作常数，否则就是O(n*logk)）。

后缀自动机的定义：对给定字符串s的后缀自动机是一个最小化确定有限状态自动机，它能够接收字符串s的所有后缀。

后缀自动机构建过程：

（1）我们将会在这里展示一些简单的字符串的后缀自动机。

（2）我们用蓝色表示初始状态，用绿色表示终止状态。

对于字符串 s=Ø：

对于字符串 s=a：

对于字符串 s=aa：

对于字符串 s=ab：

对于字符串 s=abb：

对于字符串 s=abbb：

以上是后缀自动机的一些概念和内容，不知道大家有没有学会，如果有什么疑问欢迎在博客里提出。