跳到主要内容

后缀自动机

后缀自动机（Suffix Automaton）是一种用于处理字符串的强大数据结构。它能够高效地表示一个字符串的所有子串，并且支持多种字符串操作，如模式匹配、最长公共子串等。对于初学者来说，理解后缀自动机可能有些复杂，但通过逐步学习，你会发现它的强大之处。

什么是后缀自动机？​

后缀自动机是一个有限状态自动机，它能够接受一个字符串的所有后缀。换句话说，给定一个字符串 S，后缀自动机能够识别 S 的所有子串。它的核心思想是通过状态和转移来表示字符串的所有可能子串。

为什么需要后缀自动机？​

后缀自动机的主要优势在于它的空间和时间效率。对于一个长度为 n 的字符串，后缀自动机的状态数和转移数都是 O(n) 的。这使得它在处理大规模字符串时非常高效。

后缀自动机的构建​

构建后缀自动机的过程是一个逐步添加字符的过程。我们从一个空字符串开始，逐步添加字符，并在每一步中更新自动机的状态和转移。

构建步骤​

  1. 初始化：开始时，自动机只有一个状态，即初始状态 q0。
  2. 添加字符：对于字符串中的每个字符 c，我们更新自动机的状态和转移。
  3. 更新状态：在添加字符 c 后，我们需要检查是否需要创建新的状态，或者是否可以将现有的状态合并。

代码示例​

以下是一个简单的 Python 实现，展示了如何构建后缀自动机：

python
class SuffixAutomaton:
    def __init__(self, s):
        self.last = 0
        self.states = [{'len': 0, 'link': -1, 'next': {}}]
        for c in s:
            self.add_char(c)

    def add_char(self, c):
        cur = len(self.states)
        self.states.append({'len': self.states[self.last]['len'] + 1, 'link': -1, 'next': {}})
        p = self.last
        while p != -1 and c not in self.states[p]['next']:
            self.states[p]['next'][c] = cur
            p = self.states[p]['link']
        if p == -1:
            self.states[cur]['link'] = 0
        else:
            q = self.states[p]['next'][c]
            if self.states[p]['len'] + 1 == self.states[q]['len']:
                self.states[cur]['link'] = q
            else:
                clone = len(self.states)
                self.states.append({'len': self.states[p]['len'] + 1, 'link': self.states[q]['link'], 'next': self.states[q]['next'].copy()})
                while p != -1 and self.states[p]['next'][c] == q:
                    self.states[p]['next'][c] = clone
                    p = self.states[p]['link']
                self.states[q]['link'] = clone
                self.states[cur]['link'] = clone
        self.last = cur

# 示例用法
s = "abab"
sa = SuffixAutomaton(s)
print(sa.states)

输入和输出​

输入：字符串 "abab"

输出：构建的后缀自动机的状态列表。

实际应用​

后缀自动机在字符串处理中有广泛的应用，以下是一些常见的应用场景：

  1. 模式匹配：快速查找一个模式串是否出现在文本串中。
  2. 最长公共子串：找到两个字符串的最长公共子串。
  3. 子串计数：统计一个字符串中不同子串的数量。

示例：最长公共子串​

假设我们有两个字符串 S 和 T，我们可以使用后缀自动机来找到它们的最长公共子串。

python
def longest_common_substring(S, T):
    sa = SuffixAutomaton(S)
    v = 0
    l = 0
    best_len = 0
    best_pos = 0
    for i, c in enumerate(T):
        while v != 0 and c not in sa.states[v]['next']:
            v = sa.states[v]['link']
            l = sa.states[v]['len']
        if c in sa.states[v]['next']:
            v = sa.states[v]['next'][c]
            l += 1
        if l > best_len:
            best_len = l
            best_pos = i
    return T[best_pos - best_len + 1:best_pos + 1]

# 示例用法
S = "abab"
T = "baba"
print(longest_common_substring(S, T))  # 输出: "aba"

总结​

后缀自动机是一种强大的数据结构，能够高效地处理字符串的各种操作。通过理解其构建过程和应用场景，你可以在字符串处理问题中发挥它的优势。

附加资源​

练习​

  1. 实现一个后缀自动机，并测试其在模式匹配中的应用。
  2. 使用后缀自动机解决最长公共子串问题。
  3. 尝试扩展后缀自动机，使其支持更多的字符串操作，如子串计数。
提示

在学习后缀自动机时，建议从简单的例子开始，逐步理解其构建过程和应用场景。通过动手实践，你将更好地掌握这一强大的数据结构。