后缀自动机在字符串匹配中的应用

字数 3080 2025-12-14 19:36:00

后缀自动机在字符串匹配中的应用

后缀自动机（Suffix Automaton，SAM）是一种极其高效的数据结构，能够接受一个字符串的所有后缀，并具有最小状态数的有向无环图。它在字符串匹配、子串统计、最长公共子串等问题中有着广泛应用。下面，我将详细解释其原理、构造过程，并展示它在字符串匹配中的具体应用。

1. 基本概念与定义

首先，我们需要明确几个关键定义：

SAM 是一个有限状态自动机，它的状态（节点）代表了原字符串的某些“等价类”子串集合，而转移边（有向边）则代表了在当前子串后添加一个字符得到的新子串。
接受的语言：SAM 接受且仅接受字符串的所有后缀。也就是说，从初始状态出发，沿着转移边走，最终到达某个终止状态的路径所构成的字符串，必然是原字符串的某个后缀。
状态与转移：
- 每个状态包含一个或多个子串，这些子串具有相同的“结束位置集合”（即它们在原字符串中出现的结束索引集合是相同的）。
- 从状态 u 到状态 v 有一条标记为字符 c 的转移边，当且仅当状态 u 中的某个子串添加字符 c 后得到的新子串属于状态 v。

2. 状态与转移的构建原理

构建 SAM 的过程是增量式的，逐个添加字符。我们用 last 表示当前字符串对应的状态（即包含整个字符串的状态）。每次添加字符 c 时，我们需要考虑如何扩展现有的自动机。

关键点：

每个状态有一个 len 属性，表示该状态所代表的最长子串的长度。
每个状态有一个 link 属性（也称为后缀链接），指向另一个状态，该状态的最长子串是当前状态最短子串去掉第一个字符后得到的某个后缀。
构造算法的核心在于处理“重复”：当添加字符 c 时，如果现有状态已经存在相同的转移，我们需要避免创建等价的状态，从而保持自动机的最小性。

3. 构造算法步骤

假设我们正在构建字符串 s 的 SAM，初始时只有一个状态（初始状态，编号为 0），len=0，link=-1。然后逐个添加字符。

以字符串 "aabab" 为例，演示构建过程：

步骤 1: 初始化

状态 0: len=0, link=-1

步骤 2: 添加第一个字符 'a'

创建新状态 1，len = len[0] + 1 = 1
从 last=0 开始，添加转移 0 --a--> 1
由于状态 0 的 link=-1，我们将状态 1 的 link 设为 0
更新 last=1

步骤 3: 添加第二个字符 'a'

创建新状态 2，len = len[1] + 1 = 2
从 last=1 开始，检查状态 1 是否有字符 'a' 的转移。此时没有，所以添加转移 1 --a--> 2
现在，需要找到状态 1 的 link 状态（即状态 0），检查状态 0 是否有 'a' 的转移。有，它指向状态 1。这里发生关键处理：
- 由于 len[0] + 1 == len[1]（即状态 1 的 len 正好是状态 0 的 len+1），我们不需要分裂状态，直接将状态 2 的 link 设为状态 1
更新 last=2

步骤 4: 添加第三个字符 'b'

创建新状态 3，len=3
从 last=2 开始，状态 2 没有 'b' 的转移，添加转移 2 --b--> 3
状态 2 的 link 是状态 1，检查状态 1 是否有 'b' 的转移，没有，添加转移 1 --b--> 3
状态 1 的 link 是状态 0，检查状态 0 是否有 'b' 的转移，没有，添加转移 0 --b--> 3
由于状态 0 的 link=-1，将状态 3 的 link 设为 0
更新 last=3

步骤 5: 添加第四个字符 'a'

创建新状态 4，len=4
从 last=3 开始，状态 3 没有 'a' 的转移，添加转移 3 --a--> 4
状态 3 的 link 是状态 0，检查状态 0 是否有 'a' 的转移，有，它指向状态 1。此时 len[0] + 1 == len[1] 成立，所以直接将状态 4 的 link 设为状态 1
更新 last=4

步骤 6: 添加第五个字符 'b'

创建新状态 5，len=5
从 last=4 开始，状态 4 没有 'b' 的转移，添加转移 4 --b--> 5
状态 4 的 link 是状态 1，检查状态 1 是否有 'b' 的转移，有，它指向状态 3。此时，需要判断是否分裂状态：
- 由于 len[1] + 1 != len[3]（len[1]=1, len[3]=3，1+1=2 ≠ 3），说明状态 3 不仅包含从状态 1 转移来的子串，还包含其他更长的子串。因此，我们需要分裂状态 3。
- 创建新状态 6，复制状态 3 的所有转移，len[6] = len[1] + 1 = 2
- 将状态 3 的 link 设为状态 6，状态 5 的 link 设为状态 6
- 重定向状态 1 和状态 4 对状态 3 的 'b' 转移到状态 6
更新 last=5

至此，SAM 构建完成。最终的状态数为 7（0 到 6），转移边如图所示（可自行绘制）。

4. 在字符串匹配中的应用

问题：给定一个文本串 T 和一个模式串 P，判断 P 是否是 T 的子串。

传统方法：KMP 算法可以在 O(|T|+|P|) 时间内解决，但 SAM 提供了另一种灵活的方式，特别是当文本串固定、模式串多个时，SAM 优势明显。

步骤：

预处理文本串 T，构建其后缀自动机 SAM(T)。构建时间复杂度为 O(|T|)，空间复杂度为 O(|T|·Σ)（其中 Σ 是字符集大小，可通过哈希表优化）。
对于每个模式串 P，在 SAM 上进行匹配：
- 从初始状态 0 开始，依次读取 P 的每个字符。
- 如果当前状态存在对应字符的转移，则转移到新状态，并继续。
- 如果某个字符没有对应的转移，则说明 P 不是 T 的子串，匹配失败。
- 如果成功走完 P 的所有字符，则说明 P 是 T 的子串。

示例：文本串 T = "aabab"，模式串 P = "aba"。

在 SAM(T) 上匹配：
- 初始状态 0，读 'a'，转移到状态 1
- 状态 1，读 'b'，转移到状态 3
- 状态 3，读 'a'，转移到状态 4
- 成功走完，因此 "aba" 是 "aabab" 的子串。

时间复杂度：

构建 SAM: O(|T|)
每次匹配: O(|P|)
因此，对于多个模式串，总时间复杂度为 O(|T| + Σ|P_i|)，非常高效。

5. 优势与扩展

子串检查：如上所述，快速判断子串。
统计子串出现次数：通过预处理每个状态的“结束位置计数”，可以在匹配过程中快速得到子串出现次数。
最长公共子串：对两个字符串构建 SAM，可以在线性时间内求解。
最小表示法：通过 SAM 可以找到循环串的最小表示。

6. 总结

后缀自动机是一个功能强大的字符串处理工具，它以线性的时间和空间构建，能够高效处理多种字符串问题。在字符串匹配中，SAM 提供了预处理文本串、快速查询多个模式串的解决方案，特别适合于模式串多变的场景。理解和掌握 SAM 的构造与匹配过程，是深入字符串算法的关键一步。

后缀自动机在字符串匹配中的应用后缀自动机（Suffix Automaton，SAM）是一种极其高效的数据结构，能够接受一个字符串的所有后缀，并具有最小状态数的有向无环图。它在字符串匹配、子串统计、最长公共子串等问题中有着广泛应用。下面，我将详细解释其原理、构造过程，并展示它在字符串匹配中的具体应用。 1. 基本概念与定义首先，我们需要明确几个关键定义： SAM 是一个有限状态自动机，它的状态（节点）代表了原字符串的某些“等价类”子串集合，而转移边（有向边）则代表了在当前子串后添加一个字符得到的新子串。接受的语言：SAM 接受且仅接受字符串的所有后缀。也就是说，从初始状态出发，沿着转移边走，最终到达某个终止状态的路径所构成的字符串，必然是原字符串的某个后缀。状态与转移：每个状态包含一个或多个子串，这些子串具有相同的“结束位置集合”（即它们在原字符串中出现的结束索引集合是相同的）。从状态 u 到状态 v 有一条标记为字符 c 的转移边，当且仅当状态 u 中的某个子串添加字符 c 后得到的新子串属于状态 v 。 2. 状态与转移的构建原理构建 SAM 的过程是增量式的，逐个添加字符。我们用 last 表示当前字符串对应的状态（即包含整个字符串的状态）。每次添加字符 c 时，我们需要考虑如何扩展现有的自动机。关键点：每个状态有一个 len 属性，表示该状态所代表的最长子串的长度。每个状态有一个 link 属性（也称为后缀链接），指向另一个状态，该状态的最长子串是当前状态最短子串去掉第一个字符后得到的某个后缀。构造算法的核心在于处理“重复” ：当添加字符 c 时，如果现有状态已经存在相同的转移，我们需要避免创建等价的状态，从而保持自动机的最小性。 3. 构造算法步骤假设我们正在构建字符串 s 的 SAM，初始时只有一个状态（初始状态，编号为 0）， len=0 ， link=-1 。然后逐个添加字符。以字符串 "aabab" 为例，演示构建过程：步骤 1: 初始化状态 0: len=0 , link=-1 步骤 2: 添加第一个字符 'a' 创建新状态 1， len = len[0] + 1 = 1 从 last=0 开始，添加转移 0 --a--> 1 由于状态 0 的 link=-1 ，我们将状态 1 的 link 设为 0 更新 last=1 步骤 3: 添加第二个字符 'a' 创建新状态 2， len = len[1] + 1 = 2 从 last=1 开始，检查状态 1 是否有字符 'a' 的转移。此时没有，所以添加转移 1 --a--> 2 现在，需要找到状态 1 的 link 状态（即状态 0），检查状态 0 是否有 'a' 的转移。有，它指向状态 1。这里发生关键处理：由于 len[0] + 1 == len[1] （即状态 1 的 len 正好是状态 0 的 len+1 ），我们不需要分裂状态，直接将状态 2 的 link 设为状态 1 更新 last=2 步骤 4: 添加第三个字符 'b' 创建新状态 3， len=3 从 last=2 开始，状态 2 没有 'b' 的转移，添加转移 2 --b--> 3 状态 2 的 link 是状态 1，检查状态 1 是否有 'b' 的转移，没有，添加转移 1 --b--> 3 状态 1 的 link 是状态 0，检查状态 0 是否有 'b' 的转移，没有，添加转移 0 --b--> 3 由于状态 0 的 link=-1 ，将状态 3 的 link 设为 0 更新 last=3 步骤 5: 添加第四个字符 'a' 创建新状态 4， len=4 从 last=3 开始，状态 3 没有 'a' 的转移，添加转移 3 --a--> 4 状态 3 的 link 是状态 0，检查状态 0 是否有 'a' 的转移，有，它指向状态 1。此时 len[0] + 1 == len[1] 成立，所以直接将状态 4 的 link 设为状态 1 更新 last=4 步骤 6: 添加第五个字符 'b' 创建新状态 5， len=5 从 last=4 开始，状态 4 没有 'b' 的转移，添加转移 4 --b--> 5 状态 4 的 link 是状态 1，检查状态 1 是否有 'b' 的转移，有，它指向状态 3。此时，需要判断是否分裂状态：由于 len[1] + 1 != len[3] （ len[1]=1 , len[3]=3 ， 1+1=2 ≠ 3 ），说明状态 3 不仅包含从状态 1 转移来的子串，还包含其他更长的子串。因此，我们需要分裂状态 3。创建新状态 6，复制状态 3 的所有转移， len[6] = len[1] + 1 = 2 将状态 3 的 link 设为状态 6，状态 5 的 link 设为状态 6 重定向状态 1 和状态 4 对状态 3 的 'b' 转移到状态 6 更新 last=5 至此，SAM 构建完成。最终的状态数为 7（0 到 6），转移边如图所示（可自行绘制）。 4. 在字符串匹配中的应用问题：给定一个文本串 T 和一个模式串 P ，判断 P 是否是 T 的子串。传统方法：KMP 算法可以在 O(|T|+|P|) 时间内解决，但 SAM 提供了另一种灵活的方式，特别是当文本串固定、模式串多个时，SAM 优势明显。步骤：预处理文本串 T ，构建其后缀自动机 SAM(T)。构建时间复杂度为 O(|T|)，空间复杂度为 O(|T|·Σ)（其中 Σ 是字符集大小，可通过哈希表优化）。对于每个模式串 P ，在 SAM 上进行匹配：从初始状态 0 开始，依次读取 P 的每个字符。如果当前状态存在对应字符的转移，则转移到新状态，并继续。如果某个字符没有对应的转移，则说明 P 不是 T 的子串，匹配失败。如果成功走完 P 的所有字符，则说明 P 是 T 的子串。示例：文本串 T = "aabab" ，模式串 P = "aba" 。在 SAM(T) 上匹配：初始状态 0，读 'a'，转移到状态 1 状态 1，读 'b'，转移到状态 3 状态 3，读 'a'，转移到状态 4 成功走完，因此 "aba" 是 "aabab" 的子串。时间复杂度：构建 SAM: O(|T|) 每次匹配: O(|P|) 因此，对于多个模式串，总时间复杂度为 O(|T| + Σ|P_ i|)，非常高效。 5. 优势与扩展子串检查：如上所述，快速判断子串。统计子串出现次数：通过预处理每个状态的“结束位置计数”，可以在匹配过程中快速得到子串出现次数。最长公共子串：对两个字符串构建 SAM，可以在线性时间内求解。最小表示法：通过 SAM 可以找到循环串的最小表示。 6. 总结后缀自动机是一个功能强大的字符串处理工具，它以线性的时间和空间构建，能够高效处理多种字符串问题。在字符串匹配中，SAM 提供了预处理文本串、快速查询多个模式串的解决方案，特别适合于模式串多变的场景。理解和掌握 SAM 的构造与匹配过程，是深入字符串算法的关键一步。