c- Karp-Rabin rolling hash - 跳过和追加部分

Question

我的 Karp-Rabin 算法的特定部分需要一点帮助。我想要做的是实现带有固定 sliding window 和单独的 append 和 skip 部分的版本。 Sliding window 工作得很好。当我尝试将单体 sliding window 拆分为 append 和 skip 部分时出现问题。 Append 似乎工作正常，但 skip 是最近几天让我头疼的事情。

问题 - 我正在浏览包含模式订阅实例的字符串。 Sliding window 检测到它，但未检测到其他两个。

这个想法是 RH 结构保存 (base ^ window size) mod prime number 的预计算值(b2wmod) 这样我就可以删除字符串的前导字符。随着 window 大小的变化，此值在所有 append 和 skip 之后发生变化。减少b2wmod的值，使用乘法逆不在mod删除的情况下（inverse of base mod modulus value )。它也是预先计算的。

以下是我感兴趣的部分代码。我不会post整个代码以免让您阅读所有内容，但如果需要可以上传。乘法逆似乎计算正确，但我也可以上传代码。

非常感谢任何帮助！提前致谢！

void
append_to_rh(RH rh)
{
    uint64_t hash    = rh->hash;
    uint64_t base    = rh->base;
    uint64_t mod     = rh->mod;
    uint64_t b2wmodm = rh->b2wmodm;
    char     new     = rh->new;
    
    hash             = ( hash * base + new ) % mod;    
    b2wmodm          = ( b2wmodm * base ) % mod;
    
    rh->hash         = hash;
    rh->b2wmodm      = b2wmodm;
}

void
skip(RH rh)
{
    uint64_t hash       = rh->hash;
    uint64_t base       = rh->base;
    uint64_t mod        = rh->mod;
    uint64_t b2wmodm    = rh->b2wmodm;
    uint64_t m_inv      = rh->m_inv;
    char     old        = rh->old;
    uint64_t correction = old * mod;
   
    b2wmodm = ( b2wmodm * (m_inv % mod) ) % mod;
    hash    = ( hash - old * b2wmodm + correction ) % mod;

    rh->hash    = hash;
    rh->b2wmodm = b2wmodm;
}

void
slide_window(RH rh)
{
    uint64_t base    = rh->base;
    uint64_t mod     = rh->mod;
    uint64_t hash    = rh->hash;
    uint64_t b2wmodm = rh->b2wmodm;
    char old = rh->old;
    char new = rh->new;

    hash     = ( hash * base - old * b2wmodm + new ) % mod;
    rh->hash = hash;
}

Answer 1

您的 append 和 skip 函数工作正常。这是我用来测试的示例代码

#include <string>
#include <cassert>

typedef long long ll;

ll hash, b2wmodm, base, inv_base, mod;

// fast exponentiation, for calculating inv_base
ll exp(ll a, ll b){
    ll ans = 1;
    while (b){
        if (b&1){
            ans *= a;
            ans %= mod;
        }
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return ans;
}

// calculates expected hash of the string
ll expected_hash(std::string s) {
    ll result = 0;
    ll multiplier = 1;
    for (int i = s.length()-1; i >= 0; i--) {
        result += s[i] * multiplier % mod;
        result %= mod;
        multiplier = multiplier * base % mod;
    }
    return result;
}

// same as your append and skip functions
void append_to_rh(ll newc) {
    hash = (hash * base + newc) % mod;
    b2wmodm = (b2wmodm * base) % mod;
}

void skip(ll old) {
    ll correction = old * mod;

    b2wmodm = (b2wmodm * (inv_base % mod)) % mod;
    hash = (hash - old * b2wmodm + correction) % mod;
}

int main() {

    base = 29;
    mod = 1000000007;

    hash = 0;
    b2wmodm = 1;
    inv_base = exp(base, mod-2);

    srand(time(nullptr));
    std::string s;
    for (int i = 0; i < 2000; i++) {
        if (i < 1000 || rand()%2) {
            char newchar = rand()%26 + 'a';
            s += newchar;
            append_to_rh(newchar);
            assert(expected_hash(s) == hash);
        } else {
            char oldchar = s[0];
            s = s.substr(1, s.length());
            skip(oldchar);
            assert(expected_hash(s) == hash);
        }
    }
}

我猜你的代码的其他部分会导致问题。也许您正在尝试跳过一个空 window，或者您可能使用一个非素数 mod.

c- Karp-Rabin rolling hash - 跳过和追加部分

c- Karp-Rabin rolling hash - skip and append parts

c

algorithm

rabin-karp