string - 什么是后缀自动机？

Question

有人可以向我解释一下后缀自动机到底是什么，它是如何工作的以及与后缀树和后缀数组的区别？我已经尝试在网上搜索，但无法找到任何清晰全面的解释。

我发现以下链接最接近我想要的，但它是俄文的，翻译成英文很难理解。

http://e-maxx.ru/algo/suffix_automata

Answer 1

后缀自动机是一种识别字符串所有后缀的有限状态机。您可以阅读大量关于有限状态机的资源，维基百科是一个好的开始。

后缀树和后缀数组是包含字符串所有后缀的数据结构。有多种算法可以构建和作用于这些结构，以有效地对字符串执行操作。

Answer 2

后缀机：

后缀机（或词的有向无环图）是一种强大的数据结构，可以解决许多字符串问题。

例如，使用机器的后缀，您可以将一个字符串的所有出现搜索到另一个字符串中，或​​者计算给定字符串的不同子字符串的数量——这两个任务都可以在线性时间内解决。

在直观的层面上，后缀自动机可以理解为关于给定字符串的所有子字符串的简明信息。一个令人印象深刻的事实是，后缀自动机以如此简洁的形式包含所有信息，对于长度为 n 的字符串，它只需要 O(n) 内存。此外，它也可以随着时间 O(n) 构建（如果我们考虑字母 k 的大小为常数；否则，在 O (n log k) 期间）。

历史上，机器的第一个线性尺寸后缀于 1983 年 Blumer 等人开放，并在 1985 - 1986 年提出了第一个建立在线性时间的算法（Crochemore、Blumer 等人）。有关详细信息，请参阅文章末尾的参考资料。

在英语中，后缀机称为“后缀自动机”（复数形式-“后缀自动机”），而有向无环图则称为“有向无环词图”（或简称“DAWG”）。

后缀自动机的定义：

定义。给定字符串 s 的后缀自动机称为最小确定性有限自动机，它接受字符串 s 的所有后缀。

我们将解释这个定义。

• 后缀自动机是一个有向无环图，其中的顶点称为状态，图的弧是这些状态之间的转移
  。
• 其中一个状态 t_0 称为初始状态，它必须是图的原点（即所有其他状态都可以实现）。
• 自动机中的每个转换都用一些符号标记。源自任何状态的所有转换都必须具有不同的标签。（另一方面，可能不是任何字符的过渡。）
• 标记为终止状态的一种或多种情况。如果我们从初始状态 t_0 以任何方式进入任何终止状态，并让我们
  写下所有遍历的弧的标签，你会得到一个字符串，它必须是
  字符串 s 的后缀之一。
• 后缀自动机包含满足上述条件的所有机器中的最小顶点数。（
  不需要最小转换次数，因为
  机器中状态数量最小的条件可能不是“额外”
  方式 - 否则会破坏先前的属性。）

后缀自动机的基本性质：

后缀自动机最简单但最重要的属性是它包含有关字符串 s 的所有子字符串的信息。即，从初始状态 t_0 开始的任何路径，如果我们写出沿着该路径的弧的标签，则必然形成字符串 s 的子字符串。相反，字符串 s 的任何子字符串都对应于从初始状态 t_0 开始的某个路径。

为了简化解释，我们将说子串对应于从初始状态开始的路径，标签形成子串。相反，我们将说任何路径对应于由其弧的标签形成的一行。

在每个状态机中，后缀是从初始状态开始的一条或多条路径。假设状态对应于匹配所有这些方式的字符串集。

例子：