白话分析字符串匹配算法——Rabin-Karp算法

作者：[e-mail]

博客：blog.focus-linux.net  linuxfocus.blog.chinaunix.net

今天是《Algorithms In C》中关于字符串匹配算法中的最后一个，Rabin-Karp算法。

前面分析的KMP算法和BM算法的设计思路，都是通过前面已经比较过的字符，来对未来的匹配进行预判，实现最大的向右滑动。或者说通过这个预判，使下一次的比较更接近匹配的字符串。

而Rabin-Karp算法的设计思想也是利用前面已经匹配的字符。不过不同的是，Rabin-Karp算法不是未来这些信息去预判匹配的字符串，而是利用前面匹配字符的结果，使下一次匹配进行的更快。

——Rabin-Karp的具体实现请自行google。

为了实现这一目的，Rabin-Karp设计了一个巧妙的hash算法。首先计算pattern的hash值，然后在从sring的开头，计算相同长度字符串的hash值。若hash值相同，则表示匹配，若不同，则向右移动一位，计算新的hash值。

整个过程，与暴力的字符串匹配算法很相似，但由于计算hash值时，可以利用上一次的hash值，从而使新的hash值只需要加上新字母的计算，并减去上一次的第一个字母的计算，即可。这样相当于后面的每次匹配，只需要考虑一个新的字母，并减去一个老的字母，无疑极大的提高了效率——尤其是pattern的字符串很长的情况下。

那么这个hash是如何实现的呢？

hash(w[0 .. m-1])=(w[0]*2^m-1+ w[1]*2^m-2+···+ w[m-1]*2⁰) mod q
where q is a large number.

Then, rehash(a,b,h)= ((h-a*2^m-1)*2+b) mod q

上面给出这个hash的一个设计实。当不匹配时，rehash为再次hash的值，a为上次的第一个字母，b为新的字母。

下面小小的总结一下，这三个字符串匹配算法都是利用已经比较的字母，从中获得某些信息，从而提高自己的效率。而且思路却各不相同，我们需要去想，他们是如何去想出这个算法的。以前我也想过如何利用hash去实现字符串匹配，可是却觉得计算这个hash不一定比暴力算法高效多少。当时我有一个思路时，从要进行比较的字符串中，部分的进行hash，当hash不同，那么一定不匹配，hash相同则再进行字符串匹配。一般情况下，当不匹配时hash值都不同，所以可以减少一些不必要的匹配。但是还是没有想到今天这种算法。

参考：

1.