自动机（确定有限状态自动机）

这里的“自动机”指的是”确定有限状态自动机”。而自动机是信息学奥林匹克竞赛、计算机科学中被广泛使用的一个数学模型，其思想在许多字符串算法中都有涉及，学习自动机有助于理解上述算法，但是学习自动机前一定要先了解基础图论的相关知识，这样才更好理解自动机。

自动机（确定有限状态自动机）是由一个非空有限状态的集合Q、一个输入字母表 Σ（非空有限字符的集合）、一个转移函数（单值映射）、一个开始状态、一个接受状态（终结状态）的集合所组成的5-元组。

确定有限状态自动机一个字符接一个字符的读入一个字符串，并根据给定的转移函数一步一步的转移至下一个状态。在读完该字符串后，如果该自动机停在一个属于F的接受状态，那么它就接受该字符串，反之则拒绝该字符串。

自动机的类型有哪些？

（1）AC自动机

AC自动机接受且仅接受以指定的字符串集合中的某个元素为后缀的字符串。也就是Trie + KMP。

（2）后缀自动机

后缀自动机 接受且仅接受指定字符串的后缀。

（3）广义后缀自动机

广义后缀自动机 接受且仅接受指定的字符串集合中的某个元素的后缀。也就是 Trie + SAM。

广义 SAM 与 SAM 的关系就是 AC 自动机与 KMP 自动机的关系。

（4）回文自动机

回文自动机比较特殊，它不能非常方便地定义为自动机。

如果需要定义的话，它接受且仅接受某个字符串的所有回文子串的中心及右半部分。“中心及右边部分”在奇回文串中就是字面意思，在偶回文串中定义为一个特殊字符加上右边部分。这个定义看起来很奇怪，但它能让 PAM 真正成为一个自动机，而不仅是两棵树。

（5）序列自动机

序列自动机 接受且仅接受指定字符串的子序列。

在计算复杂性领域中，自动机是一个经典的模型，要想吃透这方面的内容，还是需要多多练习，从中找到规律。