编程导航会员会员
登录/注册

一文带你学会"Rabin-Karp算法"

大家好，我是算法学长，一个热爱分享算法知识的开发者。 算法 0 基础、校招冲刺中大厂，推荐使用算法导航：https://algo.codefather.cn/ 交互式算法学习平台，带大家系统化学习算法。

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. 在文本串上滑动窗口，对于每个位置：
    • 使用滚动哈希技术高效计算当前窗口的哈希值
    • 如果哈希值与模式串相等，则进行字符逐一比较以避免哈希冲突
    • 如果完全匹配，则找到一个匹配位置
  4. 重复步骤3，直到处理完整个文本串

核心特性

  • 基于哈希比较：通过哈希值比较代替直接字符比较
  • 滚动哈希：O(1)时间复杂度计算下一窗口的哈希值
  • 时间复杂度：平均情况O(n+m)，最坏情况O(n*m)
  • 空间复杂度：O(1)，只需常数额外空间
  • 适用范围：单模式和多模式串匹配场景，特别是多模式匹配

基础实现

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

Java实现

▼
java
复制代码
public class RabinKarp {
    private final static int PRIME = 101; // 哈希计算使用的质数
    
    public static int search(String text, String pattern) {
        int m = pattern.length();
        int n = text.length();
        
        if (m > n) return -1;
        if (m == 0) return 0;
        
        // 计算哈希乘数，等于d^(m-1) % PRIME，用于滚动哈希计算
        int h = 1;
        for (int i = 0; i < m - 1; i++) {
            h = (h * 256) % PRIME;
        }
        
        // 计算模式串和第一个窗口的哈希值
        int patternHash = 0;
        int textHash = 0;
        for (int i = 0; i < m; i++) {
            patternHash = (256 * patternHash + pattern.charAt(i)) % PRIME;
            textHash = (256 * textHash + text.charAt(i)) % PRIME;
        }
        
        // 滑动窗口，比较哈希值
        for (int i = 0; i <= n - m; i++) {
            // 哈希值相等时，检查是否真正匹配
            if (patternHash == textHash) {
                boolean match = true;
                for (int j = 0; j < m; j++) {
                    if (text.charAt(i + j) != pattern.charAt(j)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return i; // 找到匹配
                }
            }
            
            // 计算下一个窗口的哈希值
            if (i < n - m) {
                textHash = (256 * (textHash - text.charAt(i) * h) + text.charAt(i + m)) % PRIME;
                // 处理负数哈希值
                if (textHash < 0) {
                    textHash += PRIME;
                }
            }
        }
        
        return -1; // 未找到匹配
    }
    
    // 打印结果
    public static void main(String[] args) {
        String text = "ABABCABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        
        int position = search(text, pattern);
        if (position == -1) {
            System.out.println("未找到匹配");
        } else {
            System.out.println("模式串在位置 " + position + " 处匹配");
            System.out.println(text);
            // 打印指示匹配位置的指针
            for (int i = 0; i < position; i++) {
                System.out.print(" ");
            }
            System.out.println(pattern);
        }
    }
}

JavaScript 实现

▼
javascript
复制代码
function rabinKarpSearch(text, pattern) {
    const PRIME = 101; // 哈希计算使用的质数
    const m = pattern.length;
    const n = text.length;
    
    if (m > n) return -1;
    if (m === 0) return 0;
    
    // 计算哈希乘数，等于d^(m-1) % PRIME，用于滚动哈希计算
    let h = 1;
    for (let i = 0; i < m - 1; i++) {
        h = (h * 256) % PRIME;
    }
    
    // 计算模式串和第一个窗口的哈希值
    let patternHash = 0;
    let textHash = 0;
    for (let i = 0; i < m; i++) {
        patternHash = (256 * patternHash + pattern.charCodeAt(i)) % PRIME;
        textHash = (256 * textHash + text.charCodeAt(i)) % PRIME;
    }
    
    // 滑动窗口，比较哈希值
    for (let i = 0; i <= n - m; i++) {
        // 哈希值相等时，检查是否真正匹配
        if (patternHash === textHash) {
            let match = true;
            for (let j = 0; j < m; j++) {
                if (text[i + j] !== pattern[j]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                return i; // 找到匹配
            }
        }
        
        // 计算下一个窗口的哈希值
        if (i < n - m) {
            textHash = (256 * (textHash - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % PRIME;
            // 处理负数哈希值
            if (textHash < 0) {
                textHash += PRIME;
            }
        }
    }
    
    return -1; // 未找到匹配
}

// 测试
const text = "ABABCABABDABACDABABCABAB";
const pattern = "ABABCABAB";
const position = rabinKarpSearch(text, pattern);

if (position === -1) {
    console.log("未找到匹配");
} else {
    console.log(`模式串在位置 ${position} 处匹配`);
    console.log(text);
    console.log(" ".repeat(position) + pattern);
}

Python 实现

▼
python
复制代码
def rabin_karp_search(text, pattern):
    PRIME = 101  # 哈希计算使用的质数
    m = len(pattern)
    n = len(text)
    
    if m > n:
        return -1
    if m == 0:
        return 0
    
    # 计算哈希乘数，等于d^(m-1) % PRIME，用于滚动哈希计算
    h = 1
    for i in range(m - 1):
        h = (h * 256) % PRIME
    
    # 计算模式串和第一个窗口的哈希值
    pattern_hash = 0
    text_hash = 0
    for i in range(m):
        pattern_hash = (256 * pattern_hash + ord(pattern[i])) % PRIME
        text_hash = (256 * text_hash + ord(text[i])) % PRIME
    
    # 滑动窗口，比较哈希值
    for i in range(n - m + 1):
        # 哈希值相等时，检查是否真正匹配
        if pattern_hash == text_hash:
            match = True
            for j in range(m):
                if text[i + j] != pattern[j]:
                    match = False
                    break
            if match:
                return i  # 找到匹配
        
        # 计算下一个窗口的哈希值
        if i < n - m:
            text_hash = (256 * (text_hash - ord(text[i]) * h) + ord(text[i + m])) % PRIME
            # 处理负数哈希值
            if text_hash < 0:
                text_hash += PRIME
    
    return -1  # 未找到匹配

# 测试
text = "ABABCABABDABACDABABCABAB"
pattern = "ABABCABAB"
position = rabin_karp_search(text, pattern)

if position == -1:
    print("未找到匹配")
else:
    print(f"模式串在位置 {position} 处匹配")
    print(text)
    print(" " * position + pattern)

Go 实现

▼
go
复制代码
package main

import (
    "fmt"
)

func rabinKarpSearch(text, pattern string) int {
    PRIME := 101 // 哈希计算使用的质数
    m := len(pattern)
    n := len(text)
    
    if m > n {
        return -1
    }
    if m == 0 {
        return 0
    }
    
    // 计算哈希乘数，等于d^(m-1) % PRIME，用于滚动哈希计算
    h := 1
    for i := 0; i < m-1; i++ {
        h = (h * 256) % PRIME
    }
    
    // 计算模式串和第一个窗口的哈希值
    patternHash := 0
    textHash := 0
    for i := 0; i < m; i++ {
        patternHash = (256*patternHash + int(pattern[i])) % PRIME
        textHash = (256*textHash + int(text[i])) % PRIME
    }
    
    // 滑动窗口，比较哈希值
    for i := 0; i <= n-m; i++ {
        // 哈希值相等时，检查是否真正匹配
        if patternHash == textHash {
            match := true
            for j := 0; j < m; j++ {
                if text[i+j] != pattern[j] {
                    match = false
                    break
                }
            }
            if match {
                return i // 找到匹配
            }
        }
        
        // 计算下一个窗口的哈希值
        if i < n-m {
            textHash = (256*(textHash-int(text[i])*h) + int(text[i+m])) % PRIME
            // 处理负数哈希值
            if textHash < 0 {
                textHash += PRIME
            }
        }
    }
    
    return -1 // 未找到匹配
}

func main() {
    text := "ABABCABABDABACDABABCABAB"
    pattern := "ABABCABAB"
    position := rabinKarpSearch(text, pattern)
    
    if position == -1 {
        fmt.Println("未找到匹配")
    } else {
        fmt.Printf("模式串在位置 %d 处匹配\n", position)
        fmt.Println(text)
        // 打印指示匹配位置的指针
        for i := 0; i < position; i++ {
            fmt.Print(" ")
        }
        fmt.Println(pattern)
    }
}

C 实现

▼
c
复制代码
#include <stdio.h>
#include <string.h>

#define PRIME 101 // 哈希计算使用的质数

// Rabin-Karp字符串匹配算法
int rabinKarpSearch(char *text, char *pattern) {
    int m = strlen(pattern);
    int n = strlen(text);
    
    if (m > n) return -1;
    if (m == 0) return 0;
    
    // 计算哈希乘数，等于d^(m-1) % PRIME，用于滚动哈希计算
    int h = 1;
    for (int i = 0; i < m - 1; i++) {
        h = (h * 256) % PRIME;
    }
    
    // 计算模式串和第一个窗口的哈希值
    int patternHash = 0;
    int textHash = 0;
    for (int i = 0; i < m; i++) {
        patternHash = (256 * patternHash + pattern[i]) % PRIME;
        textHash = (256 * textHash + text[i]) % PRIME;
    }
    
    // 滑动窗口，比较哈希值
    for (int i = 0; i <= n - m; i++) {
        // 哈希值相等时，检查是否真正匹配
        if (patternHash == textHash) {
            int j;
            for (j = 0; j < m; j++) {
                if (text[i + j] != pattern[j]) {
                    break;
                }
            }
            if (j == m) {
                return i; // 找到匹配
            }
        }
        
        // 计算下一个窗口的哈希值
        if (i < n - m) {
            textHash = (256 * (textHash - text[i] * h) + text[i + m]) % PRIME;
            // 处理负数哈希值
            if (textHash < 0) {
                textHash += PRIME;
            }
        }
    }
    
    return -1; // 未找到匹配
}

int main() {
    char text[] = "ABABCABABDABACDABABCABAB";
    char pattern[] = "ABABCABAB";
    
    int position = rabinKarpSearch(text, pattern);
    
    if (position == -1) {
        printf("未找到匹配\n");
    } else {
        printf("模式串在位置 %d 处匹配\n", position);
        printf("%s\n", text);
        
        // 打印指示匹配位置的指针
        for (int i = 0; i < position; i++) {
            printf(" ");
        }
        printf("%s\n", pattern);
    }
    
    return 0;
}

C++ 实现

▼
cpp
复制代码
#include <iostream>
#include <string>

class RabinKarp {
private:
    const int PRIME = 101; // 哈希计算使用的质数
    
public:
    int search(const std::string& text, const std::string& pattern) {
        int m = pattern.length();
        int n = text.length();
        
        if (m > n) return -1;
        if (m == 0) return 0;
        
        // 计算哈希乘数，等于d^(m-1) % PRIME，用于滚动哈希计算
        int h = 1;
        for (int i = 0; i < m - 1; i++) {
            h = (h * 256) % PRIME;
        }
        
        // 计算模式串和第一个窗口的哈希值
        int patternHash = 0;
        int textHash = 0;
        for (int i = 0; i < m; i++) {
            patternHash = (256 * patternHash + pattern[i]) % PRIME;
            textHash = (256 * textHash + text[i]) % PRIME;
        }
        
        // 滑动窗口，比较哈希值
        for (int i = 0; i <= n - m; i++) {
            // 哈希值相等时，检查是否真正匹配
            if (patternHash == textHash) {
                bool match = true;
                for (int j = 0; j < m; j++) {
                    if (text[i + j] != pattern[j]) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return i; // 找到匹配
                }
            }
            
            // 计算下一个窗口的哈希值
            if (i < n - m) {
                textHash = (256 * (textHash - text[i] * h) + text[i + m]) % PRIME;
                // 处理负数哈希值
                if (textHash < 0) {
                    textHash += PRIME;
                }
            }
        }
        
        return -1; // 未找到匹配
    }
};

int main() {
    std::string text = "ABABCABABDABACDABABCABAB";
    std::string pattern = "ABABCABAB";
    
    RabinKarp rk;
    int position = rk.search(text, pattern);
    
    if (position == -1) {
        std::cout << "未找到匹配" << std::endl;
    } else {
        std::cout << "模式串在位置 " << position << " 处匹配" << std::endl;
        std::cout << text << std::endl;
        
        // 打印指示匹配位置的指针
        for (int i = 0; i < position; i++) {
            std::cout << " ";
        }
        std::cout << pattern << std::endl;
    }
    
    return 0;
}

优化策略

使用更好的哈希函数

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

▼
java
复制代码
public class ImprovedRabinKarp {
    private final static long PRIME1 = 1000000007; // 第一个哈希的质数
    private final static long PRIME2 = 1000000009; // 第二个哈希的质数
    
    // 使用双哈希来减少冲突
    public static int search(String text, String pattern) {
        int m = pattern.length();
        int n = text.length();
        
        if (m > n) return -1;
        if (m == 0) return 0;
        
        // 计算哈希乘数
        long h1 = 1;
        long h2 = 1;
        for (int i = 0; i < m - 1; i++) {
            h1 = (h1 * 256) % PRIME1;
            h2 = (h2 * 256) % PRIME2;
        }
        
        // 计算模式串和第一个窗口的哈希值
        long patternHash1 = 0;
        long patternHash2 = 0;
        long textHash1 = 0;
        long textHash2 = 0;
        
        for (int i = 0; i < m; i++) {
            patternHash1 = (256 * patternHash1 + pattern.charAt(i)) % PRIME1;
            patternHash2 = (256 * patternHash2 + pattern.charAt(i)) % PRIME2;
            textHash1 = (256 * textHash1 + text.charAt(i)) % PRIME1;
            textHash2 = (256 * textHash2 + text.charAt(i)) % PRIME2;
        }
        
        // 滑动窗口，比较哈希值
        for (int i = 0; i <= n - m; i++) {
            // 两个哈希都相等时，再进行字符比较
            if (patternHash1 == textHash1 && patternHash2 == textHash2) {
                boolean match = true;
                for (int j = 0; j < m; j++) {
                    if (text.charAt(i + j) != pattern.charAt(j)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return i; // 找到匹配
                }
            }
            
            // 计算下一个窗口的哈希值
            if (i < n - m) {
                textHash1 = (256 * (textHash1 - text.charAt(i) * h1) + text.charAt(i + m)) % PRIME1;
                textHash2 = (256 * (textHash2 - text.charAt(i) * h2) + text.charAt(i + m)) % PRIME2;
                
                // 处理负数哈希值
                if (textHash1 < 0) textHash1 += PRIME1;
                if (textHash2 < 0) textHash2 += PRIME2;
            }
        }
        
        return -1; // 未找到匹配
    }
}

优缺点

优点

  • 平均情况下时间复杂度为O(n+m)，接近线性时间
  • 在多模式匹配场景下效率高
  • 可以通过预处理模式串提高效率
  • 滚动哈希计算使得算法高效移动窗口
  • 实现相对简单，原理容易理解

缺点

  • 哈希冲突可能导致额外的字符比较
  • 最坏情况下的时间复杂度为O(n*m)
  • 哈希函数的选择对算法性能影响很大
  • 需要注意数值溢出问题
  • 对于短模式串和文本串，预处理开销可能抵消算法优势

应用场景

1）文档相似度检测和抄袭检测

2）网络安全中的特征码匹配

3）多模式字符串搜索引擎

4）编译器中的词法分析器

扩展

Rabin-Karp指纹算法

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

▼
java
复制代码
public class RabinKarpFingerprint {
    private final static long PRIME = 1000000007;
    private final static int WINDOW_SIZE = 5; // 指纹窗口大小
    
    public static Set<Long> generateFingerprints(String text) {
        Set<Long> fingerprints = new HashSet<>();
        int n = text.length();
        
        if (n < WINDOW_SIZE) {
            fingerprints.add(calculateHash(text, n));
            return fingerprints;
        }
        
        // 计算第一个窗口的哈希值
        long textHash = calculateHash(text, WINDOW_SIZE);
        fingerprints.add(textHash);
        
        // 计算哈希乘数
        long h = 1;
        for (int i = 0; i < WINDOW_SIZE - 1; i++) {
            h = (h * 256) % PRIME;
        }
        
        // 滑动窗口，计算所有长度为WINDOW_SIZE的子串哈希值
        for (int i = 0; i <= n - WINDOW_SIZE - 1; i++) {
            textHash = (256 * (textHash - text.charAt(i) * h) + text.charAt(i + WINDOW_SIZE)) % PRIME;
            if (textHash < 0) {
                textHash += PRIME;
            }
            fingerprints.add(textHash);
        }
        
        return fingerprints;
    }
    
    public static double calculateSimilarity(String text1, String text2) {
        Set<Long> fingerprints1 = generateFingerprints(text1);
        Set<Long> fingerprints2 = generateFingerprints(text2);
        
        // 计算交集大小
        Set<Long> intersection = new HashSet<>(fingerprints1);
        intersection.retainAll(fingerprints2);
        
        // 计算并集大小
        Set<Long> union = new HashSet<>(fingerprints1);
        union.addAll(fingerprints2);
        
        // 杰卡德相似度系数
        return (double) intersection.size() / union.size();
    }
    
    private static long calculateHash(String str, int length) {
        long hash = 0;
        for (int i = 0; i < length; i++) {
            hash = (256 * hash + str.charAt(i)) % PRIME;
        }
        return hash;
    }
}

子字符串哈希

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

▼
java
复制代码
public class SubstringHash {
    private static final long PRIME = 1000000007;
    private static final int BASE = 256;
    
    private long[] hash; // 前缀哈希值
    private long[] pow;  // BASE的幂
    private String s;    // 源字符串
    
    public SubstringHash(String s) {
        this.s = s;
        int n = s.length();
        hash = new long[n + 1];
        pow = new long[n + 1];
        
        // 预计算BASE的幂
        pow[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow[i] = (pow[i - 1] * BASE) % PRIME;
        }
        
        // 计算所有前缀的哈希值
        hash[0] = 0;
        for (int i = 0; i < n; i++) {
            hash[i + 1] = (hash[i] * BASE + s.charAt(i)) % PRIME;
        }
    }
    
    // 计算子串s[l..r]的哈希值（0-indexed）
    public long substringHash(int l, int r) {
        // 获取s[0...r]的哈希值，减去s[0...l-1]的哈希值（需要进行适当调整）
        long result = (hash[r + 1] - (hash[l] * pow[r - l + 1]) % PRIME) % PRIME;
        if (result < 0) {
            result += PRIME;
        }
        return result;
    }
    
    // 检查两个子串是否相同
    public boolean areSubstringsEqual(int l1, int r1, int l2, int r2) {
        if (r1 - l1 != r2 - l2) {
            return false; // 长度不同
        }
        return substringHash(l1, r1) == substringHash(l2, r2);
    }
}

测验

这里准备了一些测试题，方便大家判断自己的掌握情况：

  1. Rabin-Karp算法的核心思想是什么？它与朴素字符串匹配算法的主要区别是什么？
  2. 滚动哈希的计算过程是怎样的？为什么它能在O(1)时间内计算新的哈希值？
  3. 哈希冲突会对Rabin-Karp算法造成什么影响？如何减少哈希冲突？
  4. Rabin-Karp算法在多模式匹配上有什么优势？
  5. 在实际应用中，如何选择合适的哈希函数和模数？

测验答案

  1. 用哈希值进行比较。与朴素算法相比，它避免了大量不必要的字符比较，利用哈希快速筛选可能匹配的位置。
  2. 滚动哈希通过从当前哈希值中减去最左侧字符的贡献，然后加上新进入窗口字符的贡献来计算。基于数学上的多项式性质，这种计算可以在O(1)时间完成。
  3. 哈希冲突导致算法需要进行额外的字符比较，降低性能。使用更好的哈希函数、更大的质数模数或多哈希技术来减少冲突。
  4. 在多模式匹配中，Rabin-Karp可以一次性计算文本串的哈希值，然后与多个模式串的哈希值比较，避免重复扫描文本串。
  5. 选择哈希函数时应考虑计算效率和冲突概率。大多数情况下使用多项式哈希与大质数模数（如109+7或109+9）组合，在某些情况下也可以使用双哈希或多哈希技术增强安全性。

相关的 LeetCode 热门题目

给大家推荐一些可以用来练手的 LeetCode 题目：

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

学算法就上算法导航：https://algo.codefather.cn/ ，交互式算法学习平台！

算法
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
算法学长
算法学长
等级vip
内容推荐
更多
最近刷算法的一些心得~
6
Claude Code 源码架构深度解析：1884 个文件背后的 AI 编程工具设计哲学
23
深度解析 Claude Code 记忆系统：从源码看 AI 编程助手如何"记住"你的项目
6
LeetCode Hot 100 二分查找篇 - 每次砍一半，六道题从入门到穿透
2
卷AI、卷算法、2026 年的前端工程师到底在卷什么？
7
作者分享
更多
一文带你学会"最近点对问题"
4
一文带你学会"分治算法"
4
一文带你学会"KMP 算法"
6
一文带你学会"Boyer-Moore算法"
3
一文带你学会"哈希查找"
2
下载 APP