白話分析字元串比對算法——Rabin-Karp算法

作者：[email protected] 部落格：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]*2m-1+ w[1]*2m-2+···+ w[m-1]*20) mod q

where q is a large number.

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

上面給出這個hash的一個設計實。當不比對時，rehash為再次hash的值，a為上次的第一個字母，b為新的字母。

參考： 1.  http://igm.univ-mlv.fr/~lecroq/string/node5.html