1

我已经开始学习字符串处理算法，并想在 C++ 中实现 Rabin-Karp 算法。我采取了：

p = 大于字符集的素数：31 m = 模运算的素数：1e9+9

根据我能找到的，有多种实现算法的方法，我已经测试了其中两种：随着我们进入更高的索引而增加功率，以及随着我们进入更高的索引而降低功率。

例如在字符串 S[0..n-1]

令 M1 = S[0]*p^0 + S[1]*p^1 + S[2]*p^2 + ... + S[n-1]*p^n-1

令 M2 = S[0]*p^n-1 + S[1]*p^n-2 + S[2]*p^n-3 ... + S[n-1]*p^0

我已经实现了这两种方法，并且只能使用 M2 获得成功的结果。

M1 的代码：

int rabinKarpM1(string s, string t) {
    int a = (int)s.size(), b = (int)t.size();
    long long p = 31, m = 1e9+9;
    long long powTable[a] = {0};
    powTable[0] = 1;
    for (int i = 1; i < a; i++) {
        powTable[i] = powTable[i-1] * p % m;
    }

    long long hashS = 0, hashT = 0;

    for (int i = 0; i < a; i++) {
        hashS = (hashS + (s[i] - 'a' + 1)*powTable[i] % m) % m;
        hashT = (hashT + (t[i] - 'a' + 1)*powTable[i] % m) % m;
    }

    if (hashS == hashT) {
        bool match = true;
        for (int i = 0; i < a; i++) {
            if (s[i] != t[i]) {
                match = false;
                break;
            }
        }

        if (match) {
            return 0;
        }
    }

    for (int i = 0; i+a-1 < b; i++) {
        hashT = (hashT - (t[i] - 'a' + 1)) / p;
        hashT = hashT + (t[i+a] - 'a' + 1)*powTable[a-1] % m;
        hashT = hashT % m;
        if (hashS == hashT) {
            bool match = true;
            for (int j = i+1; j < a+i+1; j++) {
                if (s[j-i-1] != t[j]) {
                    match = false;
                    break;
                }
            }

            if (match) {
                return i+1;
            }
        }
    }
    return -1;
}

M2 的代码：

int rabinKarpM2(string s, string t) {
    int a = (int)s.size(), b = (int)t.size();
    long long p = 31, m = 1e9+9;
    long long powTable[a] = {0};
    powTable[0] = 1;
    for (int i = 1; i < a; i++) {
        powTable[i] = powTable[i-1] * p % m;
    }

    long long hashS = 0, hashT = 0;

    for (int i = 0; i < a; i++) {
        hashS = (hashS + (s[i] - 'a' + 1)*powTable[a-i-1] % m) % m;
        hashT = (hashT + (t[i] - 'a' + 1)*powTable[a-i-1] % m) % m;
    }

    if (hashS == hashT) {
        bool match = true;
        for (int i = 0; i < a; i++) {
            if (s[i] != t[i]) {
                match = false;
                break;
            }
        }

        if (match) {
            return 0;
        }
    }

    for (int i = 0; i+a-1 < b; i++) {
        hashT = (hashT + m - (t[i] - 'a' + 1)*powTable[a-1] % m) % m * p;
        hashT = hashT + (t[i+a] - 'a' + 1) % m;
        hashT = hashT % m;
        if (hashS == hashT) {
            bool match = true;
            for (int j = i+1; j < a+i+1; j++) {
                if (s[j-i-1] != t[j]) {
                    match = false;
                    break;
                }
            }

            if (match) {
                return i+1;
            }
        }
    }
    return -1;
}

测试输入：字符串 s = foobarfoo 字符串 t = barfoobarfoobarfoobarfoobarfoobarfoo

我在 M2 上得到了正确的结果，但在 M1 上没有。

4

0 回答 0