并行与分布式系统中的并行后缀自动机构建：基于后缀链接的高效并行化方法
字数 5755 2025-12-16 17:58:41

并行与分布式系统中的并行后缀自动机构建：基于后缀链接的高效并行化方法

问题描述

后缀自动机（Suffix Automaton，SAM）是一种强大的数据结构，它能接受一个字符串的所有后缀，并且状态数和转移数都是线性的。它广泛应用于字符串匹配、子串统计、最长公共子串等问题。给定一个长度为n的字符串S，构建其SAM的传统算法（如Ukkonen的在线构造算法）是串行的，时间复杂度为O(n)。但当n非常大时，串行构建可能成为瓶颈。我们的目标是设计一个并行算法，利用多处理器加速SAM的构建过程。

这个问题在并行与分布式计算领域的挑战在于：SAM的构建过程本质上是“在线”和“增量”的。每添加一个新字符，都需要基于前一个字符的完整SAM状态进行扩展和可能的分裂（克隆状态），这存在严格的顺序依赖。因此，我们不能简单地分割字符串独立构建再合并。我们的并行化策略将聚焦于如何“重组”这种增量依赖，将字符串分解为多个重叠的块，并行处理这些块内部的大部分构造工作，然后通过一个巧妙的合并过程，将它们整合成一个全局正确的SAM，同时保证线性的总工作量。

解题过程循序渐进讲解

我将为你详细讲解一种基于“分割-并行构建-合并”的高效并行化方法。其核心思想是将长字符串切分成有重叠的块，在每个块内部独立、并行地构建一个“局部SAM”，然后设计一个合并算法，将这些局部SAM正确地组合成全局SAM。

第一步：理解后缀自动机的核心定义与串行构建逻辑

在思考并行之前，我们必须深刻理解SAM的串行构建（这里以最常见的“增量构建”算法为例）。

  1. 状态与转移：SAM由一组状态（节点）和带字符的转移边构成。每个状态对应一个或多个“结束位置集合”（endpos集合），即子串在S中所有出现的结束位置集合。SAM有一个起始状态，以及若干终止状态（代表后缀的状态）。
  2. 后缀链接（Suffix Link, link）：这是SAM的关键。从状态v到状态u的后缀链接link(v) = u，表示状态u所代表的所有子串，是状态v所代表的最长子串的“真后缀”，并且u是所有这样的状态中代表最长子串的那一个。后缀链接构成一棵以起始状态为根的树（“链接树”或“Parent树”）。
  3. 串行增量构建步骤：从只包含起始状态（状态0）的空串SAM开始，逐个添加字符S[i]（1 ≤ i ≤ n）。
    • 设last为添加S[i-1]后表示整个前缀S[1..i-1]的状态。
    • 创建新状态cur，表示前缀S[1..i]。
    • 从last开始，沿着后缀链接向上回溯，为所有尚未包含字符S[i]转移的状态添加一条到cur的S[i]转移。
    • 如果回溯到起始状态（状态0）仍未遇到有S[i]转移的状态，则设置link(cur) = 0。
    • 否则，假设在状态p，它通过字符S[i]转移到状态q。
      • 如果len(p) + 1 == len(q)（len表示该状态所代表的最长子串长度），则简单地设置link(cur) = q。
      • 否则，需要“克隆”状态q，创建一个新状态clone，复制q的所有转移和len(clone)=len(p)+1，然后将q和cur的后缀链接都指向clone。最后，将所有原本指向q的、由字符S[i]构成的转移重定向到clone。

关键洞察：整个构建过程是顺序相关的。cur的状态创建和链接设置，严重依赖于之前所有字符处理完毕后形成的SAM拓扑以及last指针的位置。因此，直接的、无共享的并行化是不可能的。

第二步：并行化策略——重叠分块与局部SAM

我们的并行算法采取以下策略：

  1. 字符串分块：

    • 将长度为n的字符串S切分成k个连续、大致相等的块：B1, B2, ..., Bk。例如，块Bi包含字符S[(i-1)*m + 1 .. i*m]，其中m = ceil(n/k)。
    • 关键操作：重叠。为了能让块独立处理后还能正确合并，每个块在末尾需要包含下一个块的第一个字符作为“重叠区”。更精确地说，对于块Bi（除了最后一个块Bk），我们实际上处理的是子串S[(i-1)*m + 1 .. i*m + 1]。最后一个块Bk处理S[(k-1)*m + 1 .. n]。这多出来的一个字符至关重要，它包含了块边界处的“上下文”信息，使得在合并时能够处理跨越块边界的状态和转移。

  2. 并行构建局部SAM：

    • 将k个（带重叠的）子串分配给k个处理器（或线程）。
    • 每个处理器i使用标准的串行增量算法，在自己的子串Bi'（即带重叠的块）上独立构建一个完整的SAM，记作LocalSAM_i。
    • 这里有一个重要细节：构建LocalSAM_i时，其起始状态是“局部”的起始状态（我们称为local_root_i），代表空串在子串Bi'中的位置。注意：LocalSAM_i的结构和状态ID是独立于其他块的，它们之间没有关联。

  3. 识别“边界状态”：

    • 在LocalSAM_i中，我们需要标记出一类特殊的状态，称为“边界状态”（Boundary State）。
    • 定义：一个状态v是边界状态，当且仅当它代表的某个（或所有）子串的结束位置，恰好位于原始块Bi（不包含重叠的那个额外字符）的末尾。换句话说，这个状态能“看到”块Bi的结束边界。
    • 如何找到它们？在串行构建LocalSAM_i的过程中，每当我们处理完块Bi的最后一个字符（即重叠前的那个字符）时，记录下当前的last指针所指向的状态。这个状态（记作frontier_i）就是最“重要”的边界状态。实际上，从frontier_i出发，沿着后缀链接（link）路径一直回溯到局部起始状态local_root_i，这条路径上的所有状态都是边界状态。因为它们都代表了以块Bi末尾为结束位置的子串。
    • 为每个LocalSAM_i记录这个边界状态列表（或集合）BoundarySet_i。

第三步：设计全局SAM合并算法

这是并行算法的核心和最复杂的部分。我们需要将LocalSAM_1, LocalSAM_2, ..., LocalSAM_k合并成一个全局的、正确的SAM。

  1. 合并的基本思路：

    • 全局SAM的构建将模拟串行算法处理字符串S的过程，但以一种“分阶段”和“跨块链接”的方式进行。
    • 我们从LocalSAM_1开始。LocalSAM_1是基于S[1..m+1]构建的。关键观察：LocalSAM_1中，那些代表结束位置在S[1..m]内（即第一个原始块内）的子串的状态及其转移，在最终的全局SAM中已经完全正确。为什么？因为对于第一个块内的所有子串，它们的出现和上下文完全包含在LocalSAM_1的构建输入中，没有受到后面字符的影响（除了可能被块2的第一个字符影响，但那个字符作为重叠字符已经包含在内）。因此，我们可以直接将LocalSAM_1中“非边界”的部分（即那些不代表以位置m结束的子串的状态）原样复制到全局SAM中。
    • 而LocalSAM_1的边界状态（BoundarySet_1）则需要特殊处理，因为它们可能与LocalSAM_2中的状态“连接”起来。

  2. 跨块状态连接：

    • 回顾串行算法，当我们处理完S[1..m]（即第一个块的最后一个字符），状态是frontier_1。接下来串行算法会处理S[m+1]（即第二个块的第一个字符，也是我们重叠区包含的那个字符）。
    • 在并行版本中，处理S[m+1]的信息已经蕴含在LocalSAM_2中。LocalSAM_2的构建起始于一个虚拟的、代表空串在块2开始位置的状态（local_root_2）。
    • 核心操作：我们需要在全局SAM中，将代表S[1..m]的状态（即frontier_1在全局SAM中的对应状态）与代表S[m+1]的状态（即LocalSAM_2中，从local_root_2出发，经过字符S[m+1]转移到达的状态）连接起来。这本质上是在全局SAM中重建串行算法中从frontier_1到处理S[m+1]后新状态之间的转移和后缀链接关系。
    • 合并算法步骤（对于从块i合并到块i+1）：
      a. 状态映射：为LocalSAM_{i+1}的每个状态创建一个全局唯一的新ID，并在全局SAM中创建对应的状态，复制其转移函数（除了指向local_root_{i+1}的转移，因为local_root_{i+1}只是局部起始状态，不代表全局实体）。
      b. 链接重定向：对于LocalSAM_{i+1}中的边界状态v（属于BoundarySet_{i+1}），我们需要修正它的后缀链接。在LocalSAM_{i+1}中，link(v)指向LocalSAM_{i+1}内部的某个状态。在全局SAM中，v的后缀链接应该指向一个在全局SAM中、代表相同子串但结束位置更早（在块i或更前）的状态。这个目标状态可以通过查询已合并的全局SAM部分（来自LocalSAM_1到LocalSAM_i）来找到。具体方法是：根据v所代表的最长子串（可以通过len(v)和它在块i+1中的位置计算出来），在全局SAM的“链接树”中查找对应节点。这个过程可以借助在合并过程中维护的、从“子串内容”到“全局状态ID”的映射（如哈希表）来高效完成。
      c. 转移修正：类似地，对于LocalSAM_{i+1}中从边界状态v出发的某些转移，如果其目标状态是local_root_{i+1}，那么在全局SAM中，这个转移应该被重定向到全局SAM中一个正确的状态（可能是来自前面块的某个边界状态的对应状态）。
      d. 处理克隆状态：如果LocalSAM_{i+1}的内部构建过程中产生了克隆状态（由于块内字符的重复模式），这些克隆状态的结构在全局上下文中可能仍然是正确的，也可能需要调整其链接。合并算法必须能识别并正确处理这些情况，确保全局链接树的正确性。

  3. 顺序合并：

    • 上述跨块合并过程（步骤2）必须是顺序执行的：先合并LocalSAM_1到全局SAM，然后以全局SAM为基底，合并LocalSAM_2，接着合并LocalSAM_3，依此类推。
    • 这是因为合并LocalSAM_{i+1}时，需要查询和链接到已经合并到全局SAM中的、来自前i个块的状态信息。这种顺序依赖限制了合并阶段的并行度。
    • 然而，构建阶段（k个局部SAM）是完全并行的，这已经能带来显著的加速，特别是当字符串很长、块数k很大时。合并阶段虽然串行，但其时间复杂度理论上与串行构建算法同阶，为O(n)，只要常数不大，整体仍能获得接近线性的加速比。

第四步：算法总结与复杂度分析

  1. 算法步骤总览：

    • 步骤1（并行）：输入字符串S，将其划分为k个有重叠的块。
    • 步骤2（并行）：每个处理器并行地在自己的块上运行串行SAM构建算法，得到LocalSAM_i，并标记其边界状态集合BoundarySet_i。
    • 步骤3（串行合并）：初始化一个空的全局SAM。按i=1 to k的顺序，将LocalSAM_i合并到全局SAM中。合并时，创建LocalSAM_i状态的全局映射，复制其内部结构（转移），并基于边界状态和已合并的全局信息，修正后缀链接和部分跨块转移。

  2. 正确性论证：

    • 算法的正确性基于这样一个事实：对于字符串中任何一个子串，它的“第一次出现”的结束位置必然落在某个块Bi的内部（不是边界）。那么，在构建LocalSAM_i时，由于输入包含了这个结束位置以及它之后的一个字符（重叠字符），这个子串对应的状态和转移就能在LocalSAM_i中被正确地创建出来。而那些结束位置恰好位于块边界的子串（即跨块出现的后缀），其状态和链接信息则在合并过程中，通过连接前后块的边界状态被正确地建立。通过数学归纳法可以证明，最终合并得到的全局SAM与串行算法构建的SAM是同构的。

  3. 复杂度分析：

    • 时间复杂度：
      • 步骤2（并行构建）：每个处理器处理大约n/k + 1个字符，串行构建是O(字符数)，所以每个处理器本地工作量为O(n/k)。理想情况下，并行构建时间为O(n/k)。
      • 步骤3（串行合并）：合并每个LocalSAM_i需要遍历其所有状态和边，并与全局结构进行连接操作。每个局部SAM的状态数是其子串长度的线性倍，因此所有局部SAM的状态总数是O(n)。合并过程总体需要处理O(n)个状态和O(n)条边/链接。因此，合并阶段总时间为O(n)。
    • 总工作量：O(n)（构建）+ O(n)（合并）= O(n)。这与串行算法同阶，保证了工作最优性（work-efficient）。
    • 并行时间：在P个处理器上，理想并行时间为O(n/P) + O(n)。合并阶段的串行部分O(n)成为了并行加速的“瓶颈”。然而，当n远大于P，且P不太大时，O(n/P)项可能主导，算法仍能获得较好的加速效果。更高级的改进（如树形合并）可以部分缓解合并瓶颈，但实现更复杂。
    • 空间复杂度：需要存储k个局部SAM和最终的全局SAM，总空间为O(n)。

总结

这个并行后缀自动机构建算法巧妙地运用了“重叠分块”和“边界状态”的概念，将原本强顺序依赖的增量构建过程，转化为一个“高度并行的局部计算”阶段和一个“顺序但高效”的合并阶段。它展示了在面对顺序算法时，通过深入理解数据结构的内在特性（如后缀链接树的结构、子串的结束位置集合），可以设计出能够挖掘并行性的方法。这种方法的核心在于识别出可以独立处理的“本地上下文”（块内子串），并精确定义块之间必须交互的“接口信息”（边界状态及其链接），从而在保证正确性的前提下实现并行加速。

并行与分布式系统中的并行后缀自动机构建：基于后缀链接的高效并行化方法 问题描述 后缀自动机（Suffix Automaton，SAM）是一种强大的数据结构，它能接受一个字符串的所有后缀，并且状态数和转移数都是线性的。它广泛应用于字符串匹配、子串统计、最长公共子串等问题。给定一个长度为n的字符串S，构建其SAM的传统算法（如Ukkonen的在线构造算法）是串行的，时间复杂度为O(n)。但当n非常大时，串行构建可能成为瓶颈。我们的目标是设计一个并行算法，利用多处理器加速SAM的构建过程。 这个问题在并行与分布式计算领域的挑战在于：SAM的构建过程本质上是“在线”和“增量”的。每添加一个新字符，都需要基于前一个字符的完整SAM状态进行扩展和可能的分裂（克隆状态），这存在严格的顺序依赖。因此，我们不能简单地分割字符串独立构建再合并。我们的并行化策略将聚焦于如何“重组”这种增量依赖，将字符串分解为多个重叠的块，并行处理这些块内部的大部分构造工作，然后通过一个巧妙的合并过程，将它们整合成一个全局正确的SAM，同时保证线性的总工作量。 解题过程循序渐进讲解 我将为你详细讲解一种基于“分割-并行构建-合并”的高效并行化方法。其核心思想是将长字符串切分成有重叠的块，在每个块内部独立、并行地构建一个“局部SAM”，然后设计一个合并算法，将这些局部SAM正确地组合成全局SAM。 第一步：理解后缀自动机的核心定义与串行构建逻辑 在思考并行之前，我们必须深刻理解SAM的串行构建（这里以最常见的“增量构建”算法为例）。 状态与转移 ：SAM由一组状态（节点）和带字符的转移边构成。每个状态对应一个或多个“结束位置集合”（endpos集合），即子串在S中所有出现的结束位置集合。SAM有一个起始状态，以及若干终止状态（代表后缀的状态）。 后缀链接（Suffix Link, link） ：这是SAM的关键。从状态v到状态u的 后缀链接 link(v) = u ，表示状态u所代表的所有子串，是状态v所代表的最长子串的“真后缀”，并且u是所有这样的状态中代表最长子串的那一个。后缀链接构成一棵以起始状态为根的树（“链接树”或“Parent树”）。 串行增量构建步骤 ：从只包含起始状态（状态0）的空串SAM开始，逐个添加字符 S[i] （1 ≤ i ≤ n）。 设 last 为添加 S[i-1] 后表示整个前缀 S[1..i-1] 的状态。 创建新状态 cur ，表示前缀 S[1..i] 。 从 last 开始，沿着后缀链接向上回溯，为所有尚未包含字符 S[i] 转移的状态添加一条到 cur 的 S[i] 转移。 如果回溯到起始状态（状态0）仍未遇到有 S[i] 转移的状态，则设置 link(cur) = 0 。 否则，假设在状态 p ，它通过字符 S[i] 转移到状态 q 。 如果 len(p) + 1 == len(q) （ len 表示该状态所代表的最长子串长度），则简单地设置 link(cur) = q 。 否则，需要“克隆”状态 q ，创建一个新状态 clone ，复制 q 的所有转移和 len(clone)=len(p)+1 ，然后将 q 和 cur 的后缀链接都指向 clone 。最后，将所有原本指向 q 的、由字符 S[i] 构成的转移重定向到 clone 。 关键洞察 ：整个构建过程是 顺序相关 的。 cur 的状态创建和链接设置，严重依赖于之前所有字符处理完毕后形成的SAM拓扑以及 last 指针的位置。因此，直接的、无共享的并行化是不可能的。 第二步：并行化策略——重叠分块与局部SAM 我们的并行算法采取以下策略： 字符串分块 ： 将长度为n的字符串S切分成k个连续、大致相等的块： B1, B2, ..., Bk 。例如，块 Bi 包含字符 S[(i-1)*m + 1 .. i*m] ，其中 m = ceil(n/k) 。 关键操作：重叠 。为了能让块独立处理后还能正确合并，每个块在末尾需要包含下一个块的 第一个字符 作为“重叠区”。更精确地说，对于块 Bi （除了最后一个块 Bk ），我们实际上处理的是子串 S[(i-1)*m + 1 .. i*m + 1] 。最后一个块 Bk 处理 S[(k-1)*m + 1 .. n] 。这多出来的一个字符至关重要，它包含了块边界处的“上下文”信息，使得在合并时能够处理跨越块边界的状态和转移。 并行构建局部SAM ： 将k个（带重叠的）子串分配给k个处理器（或线程）。 每个处理器 i 使用标准的 串行增量算法 ，在自己的子串 Bi' （即带重叠的块）上独立构建一个完整的SAM，记作 LocalSAM_i 。 这里有一个重要细节：构建 LocalSAM_i 时，其起始状态是“局部”的起始状态（我们称为 local_root_i ），代表空串在子串 Bi' 中的位置。 注意 ： LocalSAM_i 的结构和状态ID是独立于其他块的，它们之间没有关联。 识别“边界状态” ： 在 LocalSAM_i 中，我们需要标记出一类特殊的状态，称为“边界状态”（Boundary State）。 定义 ：一个状态 v 是边界状态，当且仅当它代表的某个（或所有）子串的结束位置，恰好位于原始块 Bi （ 不包含 重叠的那个额外字符）的 末尾 。换句话说，这个状态能“看到”块 Bi 的结束边界。 如何找到它们？在串行构建 LocalSAM_i 的过程中，每当我们处理完块 Bi 的最后一个字符（即重叠前的那个字符）时，记录下当前的 last 指针所指向的状态。这个状态（记作 frontier_i ）就是最“重要”的边界状态。实际上，从 frontier_i 出发，沿着后缀链接（ link ）路径一直回溯到局部起始状态 local_root_i ，这条路径上的 所有状态 都是边界状态。因为它们都代表了以块 Bi 末尾为结束位置的子串。 为每个 LocalSAM_i 记录这个边界状态列表（或集合） BoundarySet_i 。 第三步：设计全局SAM合并算法 这是并行算法的核心和最复杂的部分。我们需要将 LocalSAM_1, LocalSAM_2, ..., LocalSAM_k 合并成一个全局的、正确的SAM。 合并的基本思路 ： 全局SAM的构建将模拟串行算法处理字符串 S 的过程，但以一种“分阶段”和“跨块链接”的方式进行。 我们从 LocalSAM_1 开始。 LocalSAM_1 是基于 S[1..m+1] 构建的。 关键观察 ： LocalSAM_1 中，那些代表结束位置在 S[1..m] 内（即第一个原始块内）的子串的状态及其转移，在最终的全局SAM中 已经完全正确 。为什么？因为对于第一个块内的所有子串，它们的出现和上下文完全包含在 LocalSAM_1 的构建输入中，没有受到后面字符的影响（除了可能被块2的第一个字符影响，但那个字符作为重叠字符已经包含在内）。因此，我们可以直接将 LocalSAM_1 中“非边界”的部分（即那些不代表以位置m结束的子串的状态）原样复制到全局SAM中。 而 LocalSAM_1 的边界状态（ BoundarySet_1 ）则需要特殊处理，因为它们可能与 LocalSAM_2 中的状态“连接”起来。 跨块状态连接 ： 回顾串行算法，当我们处理完 S[1..m] （即第一个块的最后一个字符），状态是 frontier_1 。接下来串行算法会处理 S[m+1] （即第二个块的第一个字符，也是我们重叠区包含的那个字符）。 在并行版本中，处理 S[m+1] 的信息已经蕴含在 LocalSAM_2 中。 LocalSAM_2 的构建起始于一个虚拟的、代表空串在块2开始位置的状态（ local_root_2 ）。 核心操作 ：我们需要在全局SAM中，将代表 S[1..m] 的状态（即 frontier_1 在全局SAM中的对应状态）与代表 S[m+1] 的状态（即 LocalSAM_2 中，从 local_root_2 出发，经过字符 S[m+1] 转移到达的状态） 连接 起来。这本质上是在全局SAM中重建串行算法中从 frontier_1 到处理 S[m+1] 后新状态之间的转移和后缀链接关系。 合并算法步骤 （对于从块 i 合并到块 i+1 ）： a. 状态映射 ：为 LocalSAM_{i+1} 的每个状态创建一个全局唯一的新ID，并在全局SAM中创建对应的状态，复制其转移函数（除了指向 local_root_{i+1} 的转移，因为 local_root_{i+1 }只是局部起始状态，不代表全局实体）。 b. 链接重定向 ：对于 LocalSAM_{i+1} 中的边界状态 v （属于 BoundarySet_{i+1} ），我们需要修正它的后缀链接。在 LocalSAM_{i+1} 中， link(v) 指向 LocalSAM_{i+1} 内部的某个状态。在全局SAM中， v 的后缀链接应该指向一个在全局SAM中、代表相同子串但结束位置更早（在块 i 或更前）的状态。这个目标状态可以通过查询 已合并的全局SAM部分 （来自 LocalSAM_1 到 LocalSAM_i ）来找到。具体方法是：根据 v 所代表的最长子串（可以通过 len(v) 和它在块 i+1 中的位置计算出来），在全局SAM的“链接树”中查找对应节点。这个过程可以借助在合并过程中维护的、从“子串内容”到“全局状态ID”的映射（如哈希表）来高效完成。 c. 转移修正 ：类似地，对于 LocalSAM_{i+1} 中从边界状态 v 出发的某些转移，如果其目标状态是 local_root_{i+1} ，那么在全局SAM中，这个转移应该被重定向到全局SAM中一个正确的状态（可能是来自前面块的某个边界状态的对应状态）。 d. 处理克隆状态 ：如果 LocalSAM_{i+1} 的内部构建过程中产生了克隆状态（由于块内字符的重复模式），这些克隆状态的结构在全局上下文中可能仍然是正确的，也可能需要调整其链接。合并算法必须能识别并正确处理这些情况，确保全局链接树的正确性。 顺序合并 ： 上述跨块合并过程（步骤2）必须是 顺序执行 的：先合并 LocalSAM_1 到全局SAM，然后以全局SAM为基底，合并 LocalSAM_2 ，接着合并 LocalSAM_3 ，依此类推。 这是因为合并 LocalSAM_{i+1} 时，需要查询和链接到已经合并到全局SAM中的、来自前 i 个块的状态信息。这种顺序依赖限制了合并阶段的并行度。 然而，构建阶段（k个局部SAM）是 完全并行 的，这已经能带来显著的加速，特别是当字符串很长、块数k很大时。合并阶段虽然串行，但其时间复杂度理论上与串行构建算法同阶，为O(n)，只要常数不大，整体仍能获得接近线性的加速比。 第四步：算法总结与复杂度分析 算法步骤总览 ： 步骤1（并行） ：输入字符串S，将其划分为k个有重叠的块。 步骤2（并行） ：每个处理器并行地在自己的块上运行串行SAM构建算法，得到 LocalSAM_i ，并标记其边界状态集合 BoundarySet_i 。 步骤3（串行合并） ：初始化一个空的全局SAM。按 i=1 to k 的顺序，将 LocalSAM_i 合并到全局SAM中。合并时，创建 LocalSAM_i 状态的全局映射，复制其内部结构（转移），并基于边界状态和已合并的全局信息，修正后缀链接和部分跨块转移。 正确性论证 ： 算法的正确性基于这样一个事实：对于字符串中任何一个子串，它的“第一次出现”的结束位置必然落在某个块 Bi 的内部（不是边界）。那么，在构建 LocalSAM_i 时，由于输入包含了这个结束位置以及它之后的一个字符（重叠字符），这个子串对应的状态和转移就能在 LocalSAM_i 中被正确地创建出来。而那些结束位置恰好位于块边界的子串（即跨块出现的后缀），其状态和链接信息则在合并过程中，通过连接前后块的边界状态被正确地建立。通过数学归纳法可以证明，最终合并得到的全局SAM与串行算法构建的SAM是同构的。 复杂度分析 ： 时间复杂度 ： 步骤2（并行构建）：每个处理器处理大约 n/k + 1 个字符，串行构建是O(字符数)，所以每个处理器本地工作量为O(n/k)。理想情况下，并行构建时间为O(n/k)。 步骤3（串行合并）：合并每个 LocalSAM_i 需要遍历其所有状态和边，并与全局结构进行连接操作。每个局部SAM的状态数是其子串长度的线性倍，因此所有局部SAM的状态总数是O(n)。合并过程总体需要处理O(n)个状态和O(n)条边/链接。因此，合并阶段总时间为O(n)。 总工作量 ：O(n)（构建）+ O(n)（合并）= O(n)。这与串行算法同阶，保证了工作最优性（work-efficient）。 并行时间 ：在P个处理器上，理想并行时间为O(n/P) + O(n)。合并阶段的串行部分O(n)成为了并行加速的“瓶颈”。然而，当n远大于P，且P不太大时，O(n/P)项可能主导，算法仍能获得较好的加速效果。更高级的改进（如树形合并）可以部分缓解合并瓶颈，但实现更复杂。 空间复杂度 ：需要存储k个局部SAM和最终的全局SAM，总空间为O(n)。 总结 这个并行后缀自动机构建算法巧妙地运用了“重叠分块”和“边界状态”的概念，将原本强顺序依赖的增量构建过程，转化为一个“高度并行的局部计算”阶段和一个“顺序但高效”的合并阶段。它展示了在面对顺序算法时，通过深入理解数据结构的内在特性（如后缀链接树的结构、子串的结束位置集合），可以设计出能够挖掘并行性的方法。这种方法的核心在于识别出可以独立处理的“本地上下文”（块内子串），并精确定义块之间必须交互的“接口信息”（边界状态及其链接），从而在保证正确性的前提下实现并行加速。