Rabin-Karp算法

Rabin-Karp算法是一种基于哈希函数的字符串匹配算法，由 Michael O. Rabin 和 Richard M. Karp 于1987年提出，核心思想是用哈希函数将模式串和文本串中的子串转换为数值进行比较，避免大量不必要的字符比较。这个算法特别适合多模式串匹配场景，时间复杂度平均为O(n+m)，n是文本串长度，m是模式串长度。

Rabin-Karp算法的关键在于使用滚动哈希函数（Rolling Hash），它可以在常数时间内计算出滑动窗口的新哈希值，保证算法在大多数情况下的高效性。

算法步骤

  1. 计算模式串的哈希值

  2. 计算文本串中长度为m的第一个子串的哈希值（m为模式串长度）

  3. 在文本串上滑动窗口，对于每个位置：

  • 使用滚动哈希技术高效计算当前窗口的哈希值

  • 如果哈希值与模式串相等，则进行字符逐一比较以避免哈希冲突

  • 如果完全匹配，则找到一个匹配位置

  1. 重复步骤3，直到处理完整个文本串

核心特性

  • 基于哈希比较：通过哈希值比较代替直接字符比较

  • 滚动哈希：O(1)时间复杂度计算下一窗口的哈希值

  • 时间复杂度：平均情况O(n+m)，最坏情况O(n*m)

  • 空间复杂度：O(1)，只需常数额外空间

  • 适用范围：单模式和多模式串匹配场景，特别是多模式匹配

基础实现

接下来大家一起看下Rabin-Karp算法的部分主流语言实现：

优化：使用更好的哈希函数

比如使用更复杂的哈希函数来减少冲突

优点

  • 平均情况下时间复杂度为O(n+m)，接近线性时间

  • 在多模式匹配场景下效率高

  • 可以通过预处理模式串提高效率

  • 滚动哈希计算使得算法高效移动窗口

  • 实现相对简单，原理容易理解

缺点

  • 哈希冲突可能导致额外的字符比较

  • 最坏情况下的时间复杂度为O(n*m)

  • 哈希函数的选择对算法性能影响很大

  • 需要注意数值溢出问题

  • 对于短模式串和文本串，预处理开销可能抵消算法优势

应用场景

1）文档相似度检测和抄袭检测 2）网络安全中的特征码匹配 3）多模式字符串搜索引擎 4）编译器中的词法分析器

扩展：Rabin-Karp指纹算法

Rabin-Karp算法的一个变种应用于文件相似度比较

扩展：子字符串哈希

一些编程竞赛里也使用Rabin-Karp思想进行高效的子字符串查询

相关的 LeetCode 热门题目

Rabin-Karp算法巧妙结合哈希计算和滚动窗口技术，在字符串匹配领域提供了一种高效的解决方案，特别适合多模式匹配和大规模文本处理场景。

Boyer-Moore算法

Boyer-Moore算法是一种高效的字符串匹配算法，由 Robert S. Boyer和J Strother Moore 设计于1977年。它从右向左比较字符，并利用两个启发式规则（坏字符规则和好后缀规则）在不匹配情况下实现较大跳跃，减少比较次数。Boyer-Moore算法在实际应用中大部分情况下比朴素算法和KMP算法更高效。

算法步骤

  1. 预处理模式串，构建坏字符表和好后缀表

  2. 将模式串对齐到文本串的开始位置

  3. 从模式串的最右侧字符开始比较，从右向左进行匹配

  4. 如果发生不匹配，通过以下规则计算跳转距离：

  • 坏字符规则：根据不匹配字符在模式串中的最右位置决定跳转距离

  • 好后缀规则：根据已匹配部分在模式串中的重复情况决定跳转距离

  1. 选择两个规则中的最大跳转距离，移动模式串

  2. 重复步骤3-5，直到找到匹配或到达文本串末尾

核心特性：

  • 从右向左比较：与大多数字符串匹配算法不同，从模式串的末尾开始比较

  • 双规则跳转：利用坏字符规则和好后缀规则计算跳转距离

  • 时间复杂度：最坏情况O(m*n)，m是模式串长度，n是文本串长度；平均情况接近O(n/m)

  • 空间复杂度：O(k+m)，其中k是字符集大小，m是模式串长度

  • 适用范围：特别适合长模式串和大字符集场景

基础实现

优化策略

简化好后缀表构建

对于一些应用场景，可以只使用坏字符规则，简化算法实现

缓存预计算结果

针对需要重复搜索同一模式串的场景，可以预计算并缓存结果

优点

  • 在实际应用中，大部分场景比KMP和朴素算法更高效

  • 最好情况下可以跳过大量文本，实现亚线性时间复杂度

  • 对于长模式串和大字符集特别有效

  • 预处理跟模式串有关，与文本串长度无关

缺点

  • 预处理复杂，特别是好后缀表的构建

  • 需要额外空间存储坏字符表和好后缀表

  • 最坏情况下时间复杂度仍为O(m*n)

  • 对于短模式串，预处理开销可能抵消算法优势

  • 好后缀规则的实现较复杂，容易出错

应用场景

1）文本编辑器的查找功能 2）网络安全中的特征码匹配 3）自然语言处理中的关键词检索 4）大规模文本数据处理

扩展：Horspool算法

Horspool算法是Boyer-Moore的简化版本，只使用坏字符规则，但是对坏字符表进行了修改

扩展：Sunday算法

Sunday算法是另一种Boyer-Moore的变种，它关注的是文本串中模式串后面的字符

相关的 LeetCode 热门题目

KMP算法

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，核心思想是利用已经部分匹配的信息，避免重复比较，在文本串中快速查找模式串。KMP算法特别适合处理长文本和重复性高的模式串，时间复杂度是O(m+n)，m是模式串长度，n是文本串长度。

KMP算法的关键在于构建一个部分匹配表（也叫失败函数或者next数组），这个表记录了当匹配失败时，模式串指针应该回退到的位置，让算法跳过已知不可能匹配的位置，提高匹配效率。

算法步骤

KMP算法主要分为两个阶段：

  1. 预处理阶段：计算模式串的部分匹配表（next数组）

  • 构建一个数组，记录每个位置的最长相等前后缀长度

  • 该数组用于在匹配失败时确定模式串指针的回退位置

  1. 匹配阶段：使用部分匹配表在文本串中查找模式串

  • 从左到右同时遍历文本串和模式串

  • 当字符不匹配时，根据next数组回退模式串指针

  • 当模式串完全匹配时，记录匹配位置并继续查找其他匹配

核心特性：

  • 线性时间复杂度：O(m+n)，其中m是模式串长度，n是文本串长度

  • 高效利用历史信息：通过预处理避免了重复比较

  • 只需一次遍历文本串：文本串指针不会回退

  • 空间复杂度：O(m)，仅需存储模式串的部分匹配表

  • 适用场景：特别适合长文本和具有重复性的模式串

基础实现

暴力解法

上述实现暴力枚举所有可能的匹配位置，逐一比较文本串与模式串的每个字符，直到找到完全匹配或确定不存在匹配

KMP算法的实现

在上述代码中：

是 KMP 算法的核心，在匹配失败时根据预先计算的next数组来确定模式串指针的回退位置。

优化

优化后的 next 数组

预处理减少分支实现

优点

  • 时间复杂度为O(m+n)，优于朴素的字符串匹配算法(暴力解法)

  • 文本串只需扫描一次，不会回退

  • 对于包含重复模式的字符串会高效

  • 预处理模式串，可以多次用于不同的文本串

  • 能快速跳过已知不会匹配的位置

缺点

  • 需要额外的空间存储next数组

  • 构建next数组的逻辑较为复杂，不易理解

  • 在模式串较短或无重复模式时，相比简单算法优势不明显

  • 实现时容易出错，特别是处理边界情况

应用场景

1）生物信息学中的DNA序列匹配 2）网络入侵检测系统中的模式匹配 3）搜索引擎的关键词匹配 4）数据压缩算法中的模式识别

扩展：多模式字符串匹配

相关的 LeetCode 热门题目

KMP算法是字符串处理中的经典算法，用来解决字符串匹配问题，理解它对提升算法设计能力还是很有帮助的。