在我们学习后缀自动机之前，一定要先了解什么是自动机？自动机（确定有限状态自动机）是由一个非空有限状态的集合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：
以上是后缀自动机的一些概念和内容，不知道大家有没有学会，如果有什么疑问欢迎在博客里提出。
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程