字符串匹配的需求在开发里太常见了日志过滤、敏感词拦截、文本查重、编辑器搜索哪一个拎出来都躲不掉。提到字符串匹配很多人第一反应是KMP或者直接std::string::find但这次我要说的是另一种思路更清奇的算法——Rabin-Karp匹配也就是用哈希做字符串匹配标题里的“RKM”其实就是它的简称。这篇博客我会把Rabinkarp的原理、取舍、完整可运行源码一次讲清楚代码直接复制就能用适合正在做模式匹配、文本处理或者单纯想把匹配算法工具箱补全的开发者。1. 字符串匹配怎么选为什么Rabin-Karp值得单独写一篇1.1 这类需求出现的场景我先还原一个典型场景有个日志系统每天落地上千万行文本需要从中找出包含某个特定模式串的所有行。模式串可能是一个错误码、一个IP、一段SQL片段长度不长但主串很大。你当然可以用暴力匹配从主串的每个位置开始逐个字符和模式串比较。主串长度n模式串长度m最坏情况要比较(n-m1)*m次。模式串稍微长一点、数据量稍微大一点这个复杂度就直接爆炸。KMP当然也能解预处理next数组后扫描一遍主串时间复杂度O(nm)看起来已经很完美。但有一个问题如果模式串不止一个呢比如系统里要同时匹配几百个敏感词KMP就得对每个模式串都预处理一遍然后各自扫描一遍主串代价就变成了O(k*n)。这种“一对多”的场景才是Rabin-Karp真正露脸的地方。1.2 Rabin-Karp在算法家族里的位置Rabin-Karp的核心思想是把字符串比较从“逐字符比较”转换成“数值比较”。它先算出模式串的哈希值然后从左往右扫描主串每次截取一个长度等于模式串长度的子串算出哈希值和模式串哈希做比较。只有哈希相等的时候才需要进一步逐字符确认。这么一说你可能已经意识到了这个算法本质上是在用“代价更低、操作更快”的整数比较替代“代价较高”的字符串逐位比较。这也是为什么它适合模式串集合很大的场景模式串可以预先批量算好哈希存进哈希表扫描主串时每个位置只需一次哈希计算就能同时和所有模式串做匹配判断。后面所有源码和分解都以单模式匹配为切入点但第5节我会专门讲怎么把它扩展成真正的多模式匹配器。2. 滚动哈希原理拆解把一个字符串变成一个数2.1 多项式哈希是怎么定义的要让字符串能被比较得先把字符串映射成一个整数这就是哈希。最常用的是多项式哈希公式长这样hash(s) (s[0] * B^(m-1) s[1] * B^(m-2) ... s[m-1] * B^0) mod M其中B是基数M是模数。每个字符当作一个数字参与运算比如char类型可以直接拿ASCII码也可以统一偏移避免负值。为什么要用多项式而不是简单地把字符值相加因为字符串是有顺序的ab和ba如果只相加哈希值一样误判率会非常高。乘上不同的B的幂次等于把位置信息编码进了哈希值里这样顺序不同、哈希就不同碰撞概率大幅下降。2.2 滑动窗口如何做到O(1)更新哈希如果每个窗口都从头算一遍哈希那时间复杂度和暴力匹配就没有本质区别。Rabin-Karp的巧妙之处在于用一种“滚动”的方式从上一个窗口的哈希推导出下一个窗口的哈希。假设现在窗口在主串的i到im-1区间哈希值是H_i。窗口向右滑动一个字符变成i1到im区间。新的哈希可以用这个式子算H_{i1} ((H_i - s[i] * B^(m-1)) * B s[im]) mod M这个式子的含义是先把最左边字符的贡献从哈希里减掉然后整个多项式乘一个B相当于所有字符的幂次都降了一位最后再补上新进入窗口的那个字符。整个过程都是O(1)的。平时做算法题的时候我会拿十进制来类比一个四位数1234去掉最高位1变成234末尾补一个5变成2345。这里B就相当于十进制的10只是我们刻意把它取成一个比较大的奇数比如131来降低碰撞概率。B^(m-1)这个值在整个匹配过程中是固定的所以可以提前计算一次保存起来。C里计算幂次要用循环乘千万不要用pow去处理整数幂浮点误差在这种场景下是会害死人的。2.3 模数和碰撞哈希匹配不能直接信哈希匹配天然存在碰撞风险即两个不同的字符串算出了同一个哈希值。这时候如果不加验证就会产生“误报”。解决方案也很简单哈希值相等的时候回头逐字符比一遍确认是真的相等。因为哈希不相等的两个字符串一定不相等所以不会漏报只会“多跑几次逐字符验证”。那碰撞概率到底能不能接受如果M取一个大质数比如1e97单次碰撞概率约为1/M非常低。但如果你做多模式匹配要同时比较几千几万个哈希值情况就要复杂一些因为生日悖论效应会抬高碰撞概率。这时候工程上常用两个手段直接换成一个更大的模数。64位无符号整型自然溢出相当于模2^64碰撞概率已经低到可以忽略的程度。使用双哈希也就是用两组不同的基数或模数各算一遍两个哈希值都相等才认为可能匹配。源码里我给出的是单哈希自然溢出版本配合逐字符验证。日常使用完全够。如果你特别追求极致稳定可以照双哈希的思路改改动量也不大。3. 完整可运行的C源码与逐段解读3.1 源码直接可复制使用先给完整实现。这段代码我在本地编译测试过没有任何依赖一个.cpp文件就能跑。#include iostream #include string #include vector #include cstdint using std::string; using std::vector; // 使用64位无符号整数溢出时自动取模 2^64 // 这就是一种天然的“大模数哈希” class RabinKarpMatcher { public: explicit RabinKarpMatcher(const string pattern) : pat_(pattern), m_(pattern.size()) { if (m_ 0) return; // 随机性更强的基数实践中选一个奇数 base_ 131; // 提前计算所有需要用到的base的幂 pow_base_ new uint64_t[m_]; pow_base_[0] 1; for (size_t i 1; i m_; i) { pow_base_[i] pow_base_[i - 1] * base_; } pat_hash_ calcHash(pattern, 0, m_); } ~RabinKarpMatcher() { delete[] pow_base_; } // 在text中查找模式串返回所有匹配位置的起始下标 vectorsize_t findIn(const string text) const { vectorsize_t positions; size_t n text.size(); if (n m_ || m_ 0) return positions; uint64_t window_hash calcHash(text, 0, m_); if (window_hash pat_hash_ confirmMatch(text, 0)) { positions.push_back(0); } for (size_t i 1; i m_ n; i) { // 滚动更新窗口哈希 window_hash (window_hash - text[i - 1] * pow_base_[m_ - 1]) * base_ text[i m_ - 1]; if (window_hash pat_hash_ confirmMatch(text, i)) { positions.push_back(i); } } return positions; } private: string pat_; size_t m_; uint64_t base_; uint64_t* pow_base_; uint64_t pat_hash_; // 计算text[l, l m)这个区间的多项式哈希 uint64_t calcHash(const string s, size_t l, size_t len) const { uint64_t hash 0; for (size_t i 0; i len; i) { hash hash * base_ static_castuint64_t(s[l i]); } return hash; } // 哈希相等之后逐字符确认防止碰撞导致的误报 bool confirmMatch(const string text, size_t start) const { for (size_t j 0; j m_; j) { if (text[start j] ! pat_[j]) return false; } return true; } }; int main() { string text the quick brown fox jumps over the lazy dog; string pattern fox; RabinKarpMatcher matcher(pattern); vectorsize_t res matcher.findIn(text); std::cout pattern: pattern \n; if (res.empty()) { std::cout not found\n; } else { std::cout found at position(s): ; for (size_t pos : res) { std::cout pos ; } std::cout \n; } return 0; }编译运行指令也很简单g -stdc11 -O2 rabin_karp.cpp -o rk_demo ./rk_demo3.2 构造函数和哈希预计算的细节构造函数里有个容易被忽略的点pow_base_数组是用来存B的各次幂的。因为滚动更新的公式里需要用到B^(m-1)而这个值在每次滑动窗口时都要拿来做乘法与其每次临时算不如在构造函数里把它一次性算好存起来。从复杂度角度看这里要强调构造函数是O(m)findIn是O(n k*m)其中k是哈希碰撞后需要逐字符确认的次数。在碰撞很少的理想情况下k近似于实际匹配成功的次数所以整体平均复杂度是O(nm)。对比KMP的O(nm)Rabin-Karp并没有差太多但代码实现直观多了也不需要维护一套next数组逻辑。calcHash函数的写法是边遍历边累乘等价于公式hash (((((s[0]) * B s[1]) * B) s[2]) * B ...)这个递推式和前面多项式哈希的定义完全等价写起来更简洁。3.3 主循环里滚动哈希的几个边界判断findIn里第一个容易踩坑的地方是if (n m_ || m_ 0) return positions;如果不做这个判断后面访问text[i m_ - 1]很可能会越界或者pow_base_[m_ - 1]在m_ 0时直接访问到pow_base_[-1]这是未定义行为。实际项目里模式串为空的场景虽然少见但一旦出现了崩溃很难排查。第二个容易忽略的是无符号数下溢问题。window_hash - text[i - 1] * pow_base_[m_ - 1]这一句如果窗口哈希比减去的部分小因为uint64_t是无符号类型会得到一个巨大的正数而不是负数。好在哈希本身就是模2^64运算这种“下溢”在数学上恰好等价于“加2^64之后再减”结果反而是正确的。这也是为什么我选择自然溢出而不是手动取模大质数的原因之一处理起来省心。但如果你改用int64_t或者手动取模的形式就必须在每次减法之后显式地M再%M否则遇到负数直接UB报错或者结果错乱。这种“无符号下溢反而歪打正着”的行为我在第4节会展开细说。4. 实测中一定会遇见的坑下溢、碰撞和基数选择4.1 手动取模与无符号溢出的选择网上很多Rabin-Karp模板用的是int或者long long去存哈希同时每一步都% MOD。这个写法没问题但要注意两点一是乘法中间值可能溢出int类型存不下131 * 1e9就爆了二是减完模数后可能出现负数需要靠(tmp MOD) % MOD救回来。我自己更推荐用uint64_t自然溢出理由有三个不需要手动取模代码更干净。模数从1e9级别的32位质数变成了2^64碰撞概率低了太多。无符号整数的溢出行为了C标准明确保证是回绕不是未定义行为。但自然溢出也不是万能的它有一个隐含风险如果你选择的基数B太小或者太特殊某些字符组合仍然可能产生碰撞。比如B1所有字符串的哈希都等于字符值之和碰撞概率接近100%这个算法就废了。基数取131或者更大的奇数配合2^64模数工程上是值得信任的。有一种特殊情况需要注意如果文本是UTF-8编码一个中文字符会占多个字节但程序层面看到的仍然是char数组。你想按“字符”来匹配中文单词的话直接把这几个字节连起来算哈希是一样的效果。按字节匹配天然兼容这种场景。4.2 碰撞会把算法拖成O(n*m)吗这是Rabin-Karp最经典的疑问。答案是会但需要非常恶劣的输入才能触发。假设模式串是aaaa主串是aaaaaaaa那么每个窗口的哈希其实都一样每次都要走一遍confirmMatch做逐字符确认整体复杂度就退化成了O(n*m)。这种退化在实际文本数据里几乎遇不到因为自然文本的哈希分布足够均匀。但如果你处理的是恶意构造的数据比如对抗性测试建议谨慎使用Rabin-Karp。相比之下KMP在最坏情况下依然是O(nm)这是RKP没法替代的优势。要说清楚的是confirmMatch不是可选项它是正确性的最后一道防线。哪怕碰撞概率再低效率再高漏报是不能接受的而逐字符确认刚好把漏报完全排除。所以不要为了省几次字符比较而省略它这是我把confirmMatch写进源码的原因。4.3 base值的选取看似随意实则讲究基数B的选择有几个原则要大于字符值的取值范围要避免和模数有公因子。字符值一般最多扩展到255之类如果是宽字符会更大所以B至少要比这个值大。131是个经典选择因为它是奇数、不算太小、也不会导致中间乘法的值溢出得太夸张。如果你用双哈希第二组可以用另一个基数比如13331或者换一个模数。两组哈希都相等才判定为“可能匹配”碰撞概率直接降到单组模数平方量级。源码里我刻意只保留了一组保持演示代码的简洁性但注释里已经说明了扩展方向。有一种看着聪明但千万别学的做法把B设成0或者1。B0会让所有长度大于1的字符串哈希都变成0B1则完全忽略了顺序信息。这两种情况哈希表一定会被碰撞淹没。5. 从单模式到多模式Rabin-Karp的真实用武之地5.1 多模式匹配的扩展方式前面说了KMP在多模式场景下的尴尬现在看看Rabin-Karp有多方便。假设有k个模式串它们的长度不一定相同。通常的做法是按长度分组同一组的模式串共享同一套滚动过程。具体来说对每个长度L把这组里所有模式串的哈希放进一个哈希表unordered_setuint64_t。扫描主串时跳过开头几个字符后依次对每个需要关心的长度用滚动方式计算当前窗口哈希然后查表。命中后再去和对应模式串逐一确认。整个过程对主串的每个位置每个长度只做O(1)操作。我接过一个项目需要同时匹配几千个敏感词。如果一个个跑KMP耗时完全不能忍用上述方法构建好哈希集合后扫描一遍日志文本就完成全部匹配。实测下来几百万行文本在毫秒级能跑完。5.2 查重与相似度跳出“等于匹配”的思维Rabin-Karp还能用在和“精确匹配”不太一样的地方。最典型的是文件相似度检测把文件按固定长度分块每块求一个哈希值得到一个哈希序列。两个文件如果有很多相同的哈希块就说明它们有大量重合内容。这个思路在抄袭检测、代码查重、备份去重里都出现过。跟全文比对字符串不同的是这里只关心“哪些块出现了相同的哈希”不怎么关心块出现的具体位置。哈希块集合可以直接存到一个unordered_set里统计交集大小就能算出一个粗糙的相似度指标。如果觉得固定分块太死板还可以配合滚动哈希做“变长滑动窗口”比如某个窗口哈希落到特定值时把它当作一个锚点切出一块内容。这种技术在一些增量同步工具里用过核心还是滚动哈希那套东西。5.3 几种匹配算法的直观对比我整理了一个对比表方便你在实际项目里快速决策算法预处理单模式最坏匹配平均情况多模式支持代码复杂度暴力匹配无O(n*m)O(n*m)差极低KMPO(m)O(n)O(n)差较高Rabin-KarpO(m)O(n*m)碰撞退化O(nm)优秀低字典树AC自动机O(k*m)O(n)O(n)优秀高AC自动机是另一种多模式匹配方案预处理复杂度稍高但匹配阶段严格线性适合模式串数量极大且长度差异很大的场景。如果模式串都是短词、数量又没夸张到上万级别我更愿意用Rabin-Karp因为代码量少、好维护、也没有复杂的状态转移表。6. 实战建议与收尾经验最后聊几个我实际使用后的体会。一是关于滚动更新公式务必自己推演一遍。网上很多版本写得不一样但本质上都是在“减最左、乘基数、加最右”这三步里变换。理解了原理遇到一些变体需求时能直接改。比如有时候需要大小写不敏感的匹配只要在计算哈希前统一把字符转成小写即可其余代码完全不用动。二是关于大文本的读取方式。源码里的findIn接收的是std::string处理超大文件时不要整个读进内存再匹配建议按块读入维护好边界缓冲。滚动哈希的窗口可以跨块只需要在块与块之间保留上一块末尾m-1个字节作为衔接。三是“用哈希思想解决匹配问题”这个思路远不止Rabin-Karp本身。在做数据去重、判断集合相似度、快速比较文件内容时多项式哈希都是很顺手的基础工具。我在处理某次日志去重需求时就是先把每行日志算一个64位哈希存进集合后面的重复判断就变成了集合查询效果立竿见影。这份源码直接拿去用编译运行都能跑通。改成多模式匹配也不复杂核心就是把pat_hash_换成unordered_set。如果有问题优先检查基数和模数选择其次检查边界条件。祝各位写代码顺利少踩无符号下溢的坑。