快速实现Rolling hash

我需要一个Rolling hash来搜索文件中的模式.(我正在尝试使用Rabin-Karp字符串搜索算法).

我理解一个好的Hash是如何工作的以及一个好的Rolling Hash应该如何工作但我无法弄清楚如何在滚动哈希时有效地实现除法(或逆乘法).我也读过rsync使用的是adler32的滚动版本,但这看起来不像是一个随机的哈希.

理想情况下,如果您可以指向优化的C/C++实现,那将是很棒的,但是正确方向的任何指针都会有所帮助.

Cipher的"主要基础"理念应该可以正常运行 - 尽管他发布的解决方案看起来有点粗略.

我不认为在这种方法中需要反向乘法.这是我的解决方案:

假设我们当前已经散列的字符串是"abc",我们想要追加"d"并删除"a".

就像Cipher一样,我的基本哈希算法将是:

unsigned hash(const string& s)
{
    unsigned ret = 0;
    for (int i = 0; i < s.size(); i++)
    {
        ret *= PRIME_BASE; //shift over by one
        ret += s[i]; //add the current char
        ret %= PRIME_MOD; //don't overflow
    }
    return ret;
}

现在,实现滑动:

hash1 = [0]*base^(n-1) + [1]*base^(n-2) + ... + [n-1]

我们想在最后添加一些内容并删除第一个值,所以

hash2 = [1]*base^(n-1) + [2]*base^(n-2) + ... + [n]

首先我们可以添加最后一个字母:

hash2 = (hash1 * PRIME_BASE) + newchar;
=> [0]*base^n + [1]*base^(n-1) + ... + [n-1]*base + [n]

然后简单地减去第一个字符:

hash2 -= firstchar * pow(base, n);
=> [1]*base^(n-1) + ... + [n]

一个重要的注意事项:你必须小心溢出.您可以选择让它溢出unsigned int,但我认为它更容易发生碰撞(但也更快!)

这是我的实现:

#include 
#include 
using namespace std;

const unsigned PRIME_BASE = 257;
const unsigned PRIME_MOD = 1000000007;

unsigned hash(const string& s)
{
    long long ret = 0;
    for (int i = 0; i < s.size(); i++)
    {
        ret = ret*PRIME_BASE + s[i];
        ret %= PRIME_MOD; //don't overflow
    }
    return ret;
}

int rabin_karp(const string& needle, const string& haystack)
{
    //I'm using long longs to avoid overflow
    long long hash1 = hash(needle);
    long long hash2 = 0;

    //you could use exponentiation by squaring for extra speed
    long long power = 1;
    for (int i = 0; i < needle.size(); i++)
        power = (power * PRIME_BASE) % PRIME_MOD;

    for (int i = 0; i < haystack.size(); i++)
    {
        //add the last letter
        hash2 = hash2*PRIME_BASE + haystack[i];
        hash2 %= PRIME_MOD;

        //remove the first character, if needed
        if (i >= needle.size())
        {
            hash2 -= power * haystack[i-needle.size()] % PRIME_MOD;
            if (hash2 < 0) //negative can be made positive with mod
                hash2 += PRIME_MOD;
        }

        //match?
        if (i >= needle.size()-1 && hash1 == hash2)
            return i - (needle.size()-1);
    }

    return -1;
}

int main()
{
    cout << rabin_karp("waldo", "willy werther warhol wendy --> waldo <--") << endl;
}