Rabin-Karp中的滚动哈希

Question

Rabin-Karp中的滚动哈希

3

我正在尝试实现Rabin-Karp算法以查找子字符串；但是我卡在了滚动哈希上（尝试使用维基百科中建议的公式）。

#define MOD 1000000007
unsigned long long rolling_hash(const char *str)
{
        unsigned long long hash = 0;
        size_t str_len = strlen(str);
        for(int i = 0, k = str_len -1; i < str_len; i++, k--) {
                hash = hash + str[i] * pow(257, k);
        //      hash = hash % MOD;
        }
        return hash;
}

int main(void)
{
        printf("%llu\n", rolling_hash("TestString"));
        printf("%llu\n", rolling_hash("estStringh"));
        unsigned long long old = rolling_hash("TestString");
        // Add a character to the end
        // since the last char in old was multiplied by 1, now multiply it by
        // the base and then add the _new_ character to the end
        old = old * 257 + 'h';
        //old = old % MOD;
        // Remove a char from the start
        // Simply, remove the hash value of the first character
        old = old - 'T' * pow(257, 10);;

        printf("\n%llu\n", old);
        return 0;
}

上述代码只要不使用任何余数操作就可以正常工作；一旦取消我注释的% 操作，事情就会崩溃，从滚动哈希中得到的答案将不等于第二个打印输出的答案。

janisz的答案：像janisz的回答中建议更改哈希生成器，可以使添加新字符时余数起作用，但删除旧字符时则不能。注意：我正在使用自己的pow函数来处理unsigned long long。

- Fingolfin

注释掉的那行代码有什么问题吗？%实际上是指模运算。 - Palec

@Palec：请检查已编辑的问题。（附注：%确实意味着余数，而不是模运算符）（https://dev59.com/tmox5IYBdhLWcg3wTytx） - Fingolfin

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- janisz · Accepted Answer

哈希生成器代码有误。应该是：

hash = (hash*257 + str[i]) % MOD;

请取消注释old_hash = old_hash % MOD;。同时更改生成新哈希值的方式，以前的哈希值为基础。

(old_hash - to_delete_char * pow(257, str_len-1)) % MOD;

看一下你的代码。前两行是完好无损的。循环中发生了什么。首先，你正在尽可能多地执行乘法。在我的方法中，我使用Horner算法计算哈希值，因为哈希是一个多项式。

为什么不加模数和不做任何修改时它能够工作？我认为这是巧合，因为你使用8个字符（log(2^64)/log(257)=8）溢出了整数。

现在，删除字符有什么问题。应该是to_delete_char * pow(257, str_len-1);而不是to_delete_char * pow(257, str_len);，索引应该从0而不是1开始，以匹配你的生成器。

编辑： 我认为问题出在pow函数上。正如我之前所写，它只能处理8个字符的溢出。在你的例子中，有10个字符，所以不能工作。

编辑：结果发现添加和删除字符必须作为一个操作完成。可能是由于等效性，但我不确定。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define MOD 787

unsigned long long pow(int x, int y)
{
    unsigned long long ret = 1;
    for (int i=0;i<y;i++)
        ret = (ret*x)%MOD;
    return ret;
}
unsigned long long rolling_hash(const char *str)
{
        unsigned long long hash = 0;
        size_t str_len = strlen(str);
        for(int i = 0, k = str_len -1; i < str_len; i++, k--) {
                hash = hash + (str[i] * pow(257, k))%MOD;
                hash = hash % MOD;
        }
        return hash;
}

int main(void)
{
        char input[] = "TestString";
        printf("Input: %llu\n", rolling_hash(input));
        printf("Expected: %llu\n", rolling_hash("estStringh"));
        unsigned long long old = rolling_hash(input);
        // Add a character to the end
        // and Remove a char from the start

        unsigned long long  h = (input[0] * pow(257, strlen(input)))%MOD;
        old = ((old * 257) + 'h' - h) % MOD;

        printf("Actual: %llu\n", old);
        return 0;
}