Rabin-Karp Algorithm

Rabin-Karp Algorithm

模式匹配 (Pattern Searching)

解决问题:

同样是解决字符串匹配问题的算法,即在一个长字符串中寻找模式字符串出现的位置。复杂度O(mn),m和n依次是模式串的长度和长字符串的长度,这样看起来似乎与暴力的方法(或者叫简单模式匹配方法)没有区别,但是在实际使用中,它常常被认为复杂度是O(m + n)的。

实现方法很简单,就是在暴力匹配的方法基础上加入hash值。

\(hash[c_1c_2…c_n] = c_1 * D^{n – 1} + c_2 * D^{n – 2} + … + c_n * D^1\)

其中D是字符表的大小,通俗来说,就是总共可能有多少种字符。

\(c_n\)表示一个字符,所以\(c_1…c_n\)就是一个字符串。

由于我们想要放到int中,我们会将其对Q取模,Q是一个任意素数。

由于模式串长度固定,我们刚开始在要寻找模式串的字符串中将开头前m个字符算出hash值,同时也算出模式串的hash值,接着首先比较hash值,如果一样再逐个字符比较一下, 如果不一样直接考虑下一段字符串。而这个算法优越性的核心就在于它找出了复杂度为O(1)的由上一段字符串算下一段字符串的公式:

\(hash(c_{s + 1}…c_{s + m + 1}) = (D * (hash(c_s…c{s + m}) – c_s*h) + c_{s + m + 1}) \% Q\)

其中,\(h = d^{m – 1} % Q\),可以使用快速模幂来求。

#include <iostream>
#include <string>

using namespace std;

const int D = 256;      /* D is the number of characters in the alphabet */
const int Q = 1e7 + 19;      /* a prime number */

string pat, txt;

int powMod(int x, int n) {
    int ret = 1;
    while (n) {
        if (n & 1) ret = ret * x % Q;
        x = x * x % Q;
        n >>= 1;
    }
    return ret;
}

void search() {
    int pat_len = pat.size();
    int txt_len = txt.size();
    int h = powMod(D, pat_len - 1);
    int p = 0, t = 0;
    for (int i = 0; i < pat_len; i++) {
        p = (p * D + pat[i]) % Q;
        t = (t * D + txt[i]) % Q;
    }
    for (int i = 0; i <= txt_len - pat_len; i++) {
        if (p == t) {
            int j;
            for (j = 0; j < pat_len; j++)
                if (pat[j] != txt[i + j]) break;
            if (j == pat_len) {
                /*
                 *  found the pattern string
                 *  do something here
                 */
            }
        }
        /* 算到最后一个后就不要再尝试算下一个hash了,否则会越界 */
        if (i < txt_len - pat_len)
            t = (D * (t - txt[i] * h) + txt[i + pat_len] + Q) % Q;      // 加Q防止负数
    }
}

int main(void) {

    return 0;
}

 

相关阅读:

Brute Force Pattern Search

图说Rabin-Karp字符串查找算法

 

可能会用到的:

10000019至10001659之内的大质数(素数)表