RabinKarp(RK)算法
RK算法
- O(n)
- go语言官方库(大部分情况)
其实朴素的字符串匹配算法(一个一个比对), 在概率上也是O(n)的。因为出现连续字符的情况是比较少的(e.g. aaaaab)
RK算法的基本思路: 先用哈希做一个粗略比对。当然是存在一定误判的, 当哈希匹配时再使用朴素算法判断。如此一来每次字符串比对就变成了一个整数的比对。
但是问题的关键是, 哈希算法的开销的O(n)的, 我们要考虑如何快速推导后面字符串的哈希值。怎么取哈希算法。
O(1)的哈希迭代
简单的哈希方法: $H(S) = \sum{S_i}$。 显然哈希冲突率是比较高的, 需要我们频繁重新比对。
一个合理的算法(将字符串看成一个X进制的数): $H(S) = \sum S_i X^{m-i-1} mod Y$, m是字符串长度。这时候哈希值还和字符位置相关, 为了防止累加过程移除我们还要mod Y(数论, 同余)。快速迭代: 移一位就整体乘base, 再加上移入, 减去移除。
举个例子, 字符串abcd的哈希值: H = a*X^3 + b*X^2 + c*X^1 + c
秒杀KMP
问题: 给定一个字串, 问其中的两段区间是否相同, 直接O(1)秒了。区间问题 + 前缀和原理
- 先求每个前缀的哈希值
- 因为我们将字符串看成了X进制的数我们就可以通过”前缀和”的方式求区间的值, 然后补齐到相同数量级即可
- 使用哈希的方式快速完成比较
取余优化(如何取Y)
无符号数溢出的自动回环的, 所以我们使用无符号数进行迭代就可以了。Y的话可选取2的整数次幂(不过用了无符号就不需要Y了)。
如何取X
因为取余操作的存在, X和Y存在一定的”冲突”。比如X取2, Y取2, 那么就相当于只有最后一个字符起作用, 导致冲突率居高不下。
所以上面这个例子启发我们: “XY尽量不要有倍数关系”. 结论是: X和Y应该互质
快速幂
我们的哈希算法需要很多幂运算, 可以使用快速幂优化。
漏洞攻击
如果知道X的值就可以通过精心设计比对的字符串, 使得每次比对都产生哈希冲突, 从而让算法降低到O(nm)。