Swift 中实现 Knuth-Morris-Pratt 字符串匹配：从 Z 数组到 suffixPrefix 移位表的线性时间模式搜索

Swift 中实现 Knuth-Morris-Pratt 字符串匹配：从 Z 数组到 suffixPrefix 移位表的线性时间模式搜索

【免费下载链接】swift-algorithm-clubAlgorithms and data structures in Swift, with explanations!项目地址: https://gitcode.com/gh_mirrors/sw/swift-algorithm-club

本文以 swift-algorithm-club 仓库中 Knuth-Morris-Pratt 模块 为核心，讲解如何用 Swift 实现一个线性时间的字符串模式匹配算法：先基于 Z-Algorithm 为模式串构建suffixPrefix移位表，再在搜索阶段利用该表实现大于单字符的“跳跃式”右移，从而避免冗余比较。读完本文，你将理解indexesOf(ptnr:)扩展的完整实现原理、每个关键分支的作用，以及该算法O(n + m)时间复杂度的来源。

1. 算法目标与 API 设计

模块的目标（Goal）是：用 Swift 编写一个线性时间的字符串匹配算法，返回给定模式串在文本中所有出现位置的索引（原文见 Knuth-Morris-Pratt/README.markdown）。

具体形式是实现String上的一个扩展方法indexesOf(ptnr: String) -> [Int]?：

• 返回值[Int]中每个整数代表模式串一次出现的起始下标；
• 若模式串未在文本中找到（或模式串为空），返回nil。

原文给出的两个典型示例如下，也同时出现在 KnuthMorrisPratt.playground 的 Contents.swift 末尾：

let dna = "ACCCGGTTTTAAAGAACCACCATAAGATATAGACAGATATAGGACAGATATAGAGACAAAACCCCATACCCCAATATTTTTTTGGGGAGAAAAACACCACAGATAGATACACAGACTACACGAGATACGACATACAGCAGCATAACGACAACAGCAGATAGACGATCATAACAGCAATCAGACCGAGCGCAGCAGCTTTTAAGCACCAGCCCCACAAAAAACGACAATFATCATCATATACAGACGACGACACGACATATCACACGACAGCATA" dna.indexesOf(ptnr: "CATA") // Output: [20, 64, 130, 140, 166, 234, 255, 270] let concert = "🎼🎹🎹🎸🎸🎻🎻🎷🎺🎤👏👏👏" concert.indexesOf(ptnr: "🎻🎷") // Output: [6]

第二个示例展示了该实现在多字节 emoji 场景下依然正确——因为实现中先用Array(self)把字符串转成Character数组再按索引比较，避免了 Swift 字符串按UTF-16/Unicode.Scalar索引比较的陷阱。

KMP 算法在理论上是解决模式匹配问题的最佳算法之一。文档同时指出：实践中 Boyer-Moore 系列 往往更受青睐，但 KMP 概念更简单，且具有相同的线性时间复杂度。与最朴素的 暴力字符串搜索 相比，KMP 的差别只在于：当比较发生失配（mismatch）时，不是简单地只右移一个字符，而是根据预处理得到的信息执行更大步长的移动。这种移动能力的来源，就是下一节讲的suffixPrefix数组。

2. 核心数据结构：suffixPrefix 移位表

2.1 定义

KMP 包含一个只针对模式串的预处理阶段，它产出一个整数数组（代码中命名为suffixPrefix）。设模式串为P，则：

suffixPrefix[i]记录的是P[0...i]的最长真后缀（proper suffix）中，与P的前缀相匹配的那个后缀的长度。

换句话说，suffixPrefix[i]是以位置i结尾、且同时是P的前缀的最长子串的长度。文档给出的例子：取P = "abadfryaabsabadffg"，则

• suffixPrefix[4] = 0
• suffixPrefix[9] = 2
• suffixPrefix[14] = 4

2.2 用 Z-Algorithm 构建移位表

suffixPrefix有多种求法，本仓库采用的是基于 Z-Algorithm 的路线。Z-数组的定义是：Z[i]表示P中从位置i开始、与P前缀相匹配的最长子串的长度（实现见 ZAlgorithm.swift）。

可以发现Z[i]与suffixPrefix[i]记录的是同一份信息，只是记录的位置不同：

• Z[i]从子串的起点i处记录；
• suffixPrefix从子串的终点处记录。

因此只需把Z[i]映射到suffixPrefix的正确位置即可。仓库 KnuthMorrisPratt.swift 中的映射代码只有三行：

for patternIndex in (1 ..< patternLength).reversed() { textIndex = patternIndex + zeta![patternIndex] - 1 suffixPrefix[textIndex] = zeta![patternIndex] }

其思路是：从位置i开始、长度为Z[i]的子串，其结束下标正好是i + Z[i] - 1；把Z[i]写入suffixPrefix的这个结束位置即可。

从源码结构看，使用.reversed()从大下标往小下标遍历有一层保护作用：若多个起点位置映射到同一个结束位置（即存在嵌套的重叠前缀匹配），先写入的是较短的匹配，随后较短匹配之外的更长匹配（起点更小、长度更大）会覆盖它，最终表中保留的是最长的匹配长度，这正好符合suffixPrefix的定义。

3. 完整实现逐段解析

以下是 KnuthMorrisPratt.swift 的完整实现（文件头部注明其基于 Dan Gusfield 的著作Algorithms on String, Trees and Sequences）：

extension String { func indexesOf(ptnr: String) -> [Int]? { let text = Array(self) let pattern = Array(ptnr) let textLength: Int = text.count let patternLength: Int = pattern.count guard patternLength > 0 else { return nil } var suffixPrefix: [Int] = Int var textIndex: Int = 0 var patternIndex: Int = 0 var indexes: [Int] = [Int]() /* Pre-processing stage: computing the table for the shifts (through Z-Algorithm) */ let zeta = ZetaAlgorithm(ptnr: ptnr) for patternIndex in (1 ..< patternLength).reversed() { textIndex = patternIndex + zeta![patternIndex] - 1 suffixPrefix[textIndex] = zeta![patternIndex] } /* Search stage: scanning the text for pattern matching */ textIndex = 0 patternIndex = 0 while textIndex + (patternLength - patternIndex - 1) < textLength { while patternIndex < patternLength && text[textIndex] == pattern[patternIndex] { textIndex = textIndex + 1 patternIndex = patternIndex + 1 } if patternIndex == patternLength { indexes.append(textIndex - patternIndex) } if patternIndex == 0 { textIndex = textIndex + 1 } else { patternIndex = suffixPrefix[patternIndex - 1] } } guard !indexes.isEmpty else { return nil } return indexes } }

各部分的职责如下：

1. 参数与边界检查（KnuthMorrisPratt.swift#L15-L23）：把文本与模式都转为Character数组，空模式直接返回nil。
2. 预处理阶段（KnuthMorrisPratt.swift#L30-L36）：调用ZetaAlgorithm(ptnr:)得到zeta数组，再按 2.2 节的映射规则填出suffixPrefix。注意zeta[0]未被使用，循环从下标 1 开始。
3. 搜索阶段（KnuthMorrisPratt.swift#L38-L58）：
   • 外层while条件textIndex + (patternLength - patternIndex - 1) < textLength是一个边界不变式：它保证文本中从textIndex起剩余的字符数，足够容纳模式串中尚未比较的部分（patternLength - patternIndex - 1个），从而让内层循环可以安全地做下标访问而不会越界；
   • 内层while执行从左到右的逐字符比较，两个游标同步前进；
   • 若patternIndex == patternLength，说明整串匹配成功，记录起点textIndex - patternIndex；
   • 失配后的移动分两种情况：若本次一次比较都没做成（patternIndex == 0），文本游标textIndex右移一位，从头再比；否则执行 KMP 的关键一步——patternIndex = suffixPrefix[patternIndex - 1]，即保持textIndex不动，仅把模式游标回退到suffixPrefix给出的位置。这一步的含义是：P[0...suffixPrefix[i]]这个前缀与文本中刚匹配到的一段子串的后缀天然相等，无需重新比较，因此模式串可以一次性右移超过一个字符。

这种“模式串内部回退”的写法与常见的“KMP 失配函数表”写法在数学上等价，是从源码结构看可以得出的结论：它利用的是suffixPrefix保证的“前缀—后缀自重合”性质，把每次失配后的比较浪费压到最少。

4. 一次完整匹配的推演

文档用一个小例子完整走了一遍搜索阶段，这里保留原推演。取模式串P = "ACTGACTA"（长度 8），由预处理得到的suffixPrefix为[0, 0, 0, 0, 0, 0, 3, 1]，文本T = "GCACTGACTGACTGACTAG"。

第 1 步：对齐起点，比较T[0]与P[0]（GvsA）失配。此时没有完整匹配；且因为一次成功比较都没有（patternIndex == 0分支前的判断为suffixPrefix[1 - 1] = 0），模式串右移一位，从T[1]与P[0]重新开始比较，继续失配，再移动到T[2]：

1 0123456789012345678 text: GCACTGACTGACTGACTAG textIndex: ^ pattern: ACTGACTA patternIndex: ^ suffixPrefix: 00000031

第 2 步：T[2]起开始连续匹配，一直比到位置 8。但匹配长度 7 不等于模式长度 8，不能报告出现。此时suffixPrefix发挥作用：匹配长度为 7，查suffixPrefix[7 - 1]得3，意味着P的长度为 3 的前缀ACT与刚匹配的文本子串T[2...8]的后缀必然相等，无需重新比较——模式串可以整体右移多于一位，比较从T[9]与P[3]处直接恢复：

1 0123456789012345678 text: GCACTGACTGACTGACTAG textIndex: ^ pattern: ACTGACTA patternIndex: ^ suffixPrefix: 00000031

第 3 步：继续比较直到位置 13，G与A失配。再次查表移位：

1 0123456789012345678 text: GCACTGACTGACTGACTAG textIndex: ^ pattern: ACTGACTA patternIndex: ^ suffixPrefix: 00000031

第 4 步：重新比较，这次终于走到一次完整出现，出现在文本下标17 - 7 = 10：

1 0123456789012345678 text: GCACTGACTGACTGACTAG textIndex: ^ pattern: ACTGACTA patternIndex: ^ suffixPrefix: 00000031

第 5 步：报告出现后，算法尝试比较T[18]与P[1]（因为使用了suffixPrefix[8 - 1] = 1），比较失败，下一次外层循环的条件不满足，算法结束。整个过程中，suffixPrefix两次帮助避免了逐字符重比，这正是 KMP 线性时间的微观来源。

5. 复杂度分析

原文给出的复杂度结论与推导要点：

• 预处理阶段只涉及模式串：Z-Algorithm 的运行时间为线性，即O(n)，n为模式串P的长度；
• 搜索阶段不会“越过”文本长度m，并且可以证明搜索阶段的比较次数上界为2 * m——每次比较要么让textIndex前进，要么让匹配前缀回退到suffixPrefix的更短位置，两者都无法无限消耗；
• 因此 KMP 的总运行时间为O(n + m)。

对比之下，暴力搜索在最坏情况下（如文本全是A、模式为AAA...B）退化到O(n * m)量级的比较次数；KMP 通过suffixPrefix表把这种最坏情况消除掉了。

6. 如何运行与使用

仓库提供了两种运行方式（与原文 Note 一致）：

1. Playground 方式（推荐）：用 Xcode 打开 KnuthMorrisPratt.playground。该 Playground 的Contents.swift已内置ZetaAlgorithm函数定义（Knuth-Morris-Pratt/KnuthMorrisPratt.playground/Contents.swift#L3-L57）以及indexesOf(ptnr:)扩展，末尾还附带 DNA 与 emoji 两组示例，直接执行即可看到输出。
2. 独立文件方式：若单独使用 KnuthMorrisPratt.swift，必须把 Z-Algorithm 文件夹下的 ZAlgorithm.swift 一并复制到同一模块中，因为它依赖其中的ZetaAlgorithm函数。

使用时的几个细节：

• 方法签名为indexesOf(ptnr:)（参数标签写作ptnr），返回[Int]?；注意它与 Z-Algorithm 模块 中的indexesOf(pattern:)参数标签不同，两者是同一仓库内两个独立的线性时间方案：前者是 KMP，后者是“Z-函数拼接P$T后扫描”的变体（见 ZetaAlgorithm.swift）；
• 预处理函数ZetaAlgorithm的参数标签为ptrn（见 ZAlgorithm.swift#L11）；
• 仓库中 KnuthMorrisPratt.swift 使用Array(self)（Swift 5 的Character序列），而 Playground 副本中保留了较早期的Array(self.characters)写法，两者在现代 Swift 中均可工作，但移植时建议统一为Array(self)。

7. 小结与延伸阅读

本文实现的 KMP 方案可概括为三步：用 Z-Algorithm 得到Z数组 → 按i + Z[i] - 1映射为suffixPrefix移位表 → 搜索阶段用“文本游标只前进、模式游标按表回退”的策略完成线性扫描。suffixPrefix表是连接“失配信息”与“大跨步移位”的桥梁，也是理解 KMP 正确性的关键。

仓库中可继续深入的相关实现：

• Z-Algorithm/README.markdown：ZetaAlgorithm的完整原理与 Z-box 推演，以及“Z-函数 + 分隔符拼接”这一更简单的线性匹配方案；
• Boyer-Moore-Horspool/README.markdown：实践中更常用的右到左匹配算法；
• Brute-Force String Search/BruteForceStringSearch.swift：作为 KMP 改进起点的朴素实现。

本模块代码基于 Dan Gusfield 的著作Algorithms on String, Trees and Sequences: Computer Science and Computational Biology（Cambridge University Press, 1997），由 Matteo Dunnhofer 为 Swift Algorithm Club 编写。

【免费下载链接】swift-algorithm-clubAlgorithms and data structures in Swift, with explanations!项目地址: https://gitcode.com/gh_mirrors/sw/swift-algorithm-club