Rabin-Karp字符串匹配算法

[wuyongxiu]

Rabin-Karp字符串匹配算法是对每一个字符进行比较，把每个字符进行对应进制数并取模运算，然后比较每个字符的函数值。预处理时间是O(m)，匹配时间是O((n-m+1)m)。

Rabin-Karp算法的思想：

1 假设目标字符串长度为N，待匹配字符串的长度为M （M<=N）；

2 首先计算待匹配字符串的hash值，然后计算目标字符串前M个字符的hash值；

3 比较前面计算的2个hash值，比较次数N-M+1;

  1 若hash值不相等，则继续计算目标字符串的下一个长度为M的字符子串的hash值

  2 若hash值相同，则需要使用朴素算法再次判断是否为相同的字符串。

这里有一段关于Rabin-Karp算法的分析：

Rabin-Karp算法相对于朴素字符串匹配算法比较快的原因有2点：

① Rabin-Karp算法是将字符串计算成了数值，数值的比较 相比于对字符串的包含的字符进行逐个比较（朴素字符串匹配算法）会更快。

② 朴素字符串匹配每一次都是2个字符串的重新匹配，之前的字符串的匹配结果不能应用到这次匹配中。而Rabin-Karp可以利用上次匹配的结果信息： 字符串生成的数值可以表示出字符的前后顺序，而且可以随时去掉某个字符的值，可以随时添加一个新字符的值。当一次匹配结束后，去掉源串第一个字符的的值，再加上这次比较来自于源串中要新加的字符串的值。

Rabin-Karp算法举例：

比如我们要在源串 "9876543210520" 中查找 "520"，因为这些字符串中只有数字，所以我们可以使用字符集 {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'} 来表示字符串中的所有元素，并且将各个字符映射到数字 0～9，然后用 M 表示字符集中字符的总个数，这里是 10，那么我们就可以将搜索词 "520" 转化为下面的数值：

("5"的映射值 * M + "2"的映射值) * M + "0"的映射值 = (5 * 10 + 2) * 10 + 0 = 520

“搜索词”计算好了，那么接下来计算“源串”，取“源串”的前 n 个字符（n 为“搜索词”的长度）"987"，按照同样的方法计算其数值：

("9"的映射值 * M + "8"的映射值) * M + "7"的映射值 = (9 * 10 + 8) * 10 + 7 = 987
然后将该值与搜索词的值进行比较即可。

比较发现 520 与 987 不相等，则说明 "520" 与 "987" 不匹配，则继续向下寻找，这时候该如何做呢？下一步应该比较 "520" 跟 "876" 了，那么我们如何利用前一步的信息呢？首先我们把 987 减去代表字符 "9" 的部分：

987 - ("9"的映射值 * (M 的 n - 1 次方)) = 987 - (9 * (10 的 2 次方)) = 987 - 900 = 87

然后再乘以 M（这里是 10），再加上 "6" 的映射值，不就成了 876 了么：

87 * M + "6"的映射值 = 87 * 10 + 6 = 876

再进行比较。

参考文档：
http://www.cnblogs.com/golove/p/3234673.html
https://github.com/gopher-learning/night-reading-go/blob/master/20180510/README.md
https://blog.csdn.net/chenhanzhun/article/details/39895077
https://github.com/gopher-learning/night-reading-go/blob/master/20180510/README.md