Rabin-Karp字符串匹配算法详解（C#实现滚动哈希高效查找子串）

滚动哈希原理

假设我们要在文本 "abcdef" 中查找模式 "bcd"。我们可以先计算 "abc" 的哈希值，然后通过一个巧妙的数学公式，快速得到 "bcd" 的哈希值，而无需重新遍历整个子串。

常用哈希函数为：

hash(s) = (s[0] * d^(m-1) + s[1] * d^(m-2) + ... + s[m-1]) % q

其中：

• d 是字符集大小（例如ASCII为256）
• m 是模式串长度
• q 是一个大质数，用于防止整数溢出

C#实现Rabin-Karp算法

下面是一个完整的C#实现，包含详细注释：

using System;using System.Collections.Generic;class RabinKarpMatcher{    // 字符集大小（ASCII）    private const int d = 256;    /// <summary>    /// 使用Rabin-Karp算法在text中查找所有pattern出现的位置    /// </summary>    public static List<int> Search(string pattern, string text)    {        var result = new List<int>();        int m = pattern.Length;        int n = text.Length;        if (m == 0 || n == 0 || m > n)            return result;        // 选择一个大质数作为模数        int q = 101;        // 计算 d^(m-1) % q        long h = 1;        for (int i = 0; i < m - 1; i++)            h = (h * d) % q;        // 计算pattern和text前m个字符的哈希值        long patternHash = 0;        long textHash = 0;        for (int i = 0; i < m; i++)        {            patternHash = (d * patternHash + pattern[i]) % q;            textHash = (d * textHash + text[i]) % q;        }        // 滑动窗口遍历text        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)                    result.Add(i);            }            // 计算下一个窗口的哈希值（滚动哈希）            if (i < n - m)            {                textHash = (d * (textHash - text[i] * h) + text[i + m]) % q;                // 确保哈希值为正数                if (textHash < 0)                    textHash += q;            }        }        return result;    }    // 测试示例    static void Main()    {        string text = "ABABCABABA";        string pattern = "ABA";                var positions = Search(pattern, text);                Console.WriteLine($"在文本 '{text}' 中查找模式 '{pattern}'：");        if (positions.Count > 0)        {            Console.WriteLine("匹配位置: " + string.Join(", ", positions));        }        else        {            Console.WriteLine("未找到匹配项。");        }    }}

算法关键点解析

1. 哈希冲突处理：即使两个不同字符串的哈希值相同（哈希冲突），我们仍需逐字符比较确认是否真正匹配。

2. 滚动哈希更新：通过公式 textHash = (d * (textHash - text[i] * h) + text[i + m]) % q 实现O(1)时间复杂度的哈希更新。

3. 模运算优化：使用质数q可减少冲突概率；同时注意处理负数哈希值。

应用场景与优势

Rabin-Karp算法特别适合以下场景：

• 需要同时查找多个模式串（如敏感词过滤）
• 文本数据量大，但模式串较短
• 允许一定误报率的近似匹配（配合布隆过滤器等）

相比KMP或Boyer-Moore等算法，Rabin-Karp在多模式匹配中更具优势，且实现相对简单。

总结

通过本教程，你已经掌握了Rabin-Karp算法的核心思想、滚动哈希的实现技巧，以及如何用C#字符串匹配解决实际问题。记住，理解模式匹配算法不仅能提升编程能力，还能在面试和实际项目中大显身手！

动手试试修改上面的代码，在更大的文本中测试性能，或者尝试用不同的质数q观察效果变化吧！