在Rabin-Karp滚动哈希

我正在尝试使用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

Answer 1

哈希发电机代码是错误的。 它应该是

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

和unncoment 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); 应该是to_delete_char * pow(257, str_len-1); index应该从0开始，而不是从发电机开始。

编辑：我认为问题是在powfunction。 正如我上面所写，它溢出只有8个字符。 在你的例子中，你有10个，所以它无法工作。

编辑：事实certificate，添加和删除字符必须作为一个操作完成。 可能是由于等价物，但我不确定。

 #include  #include  #include  #include  #define MOD 787 unsigned long long pow(int x, int y) { unsigned long long ret = 1; for (int i=0;i 

Answer 2

我认为，使用pow（）是缓慢且危险的，因为它返回双值，而对于长字符串，可能存在计算错误（双精度错误），并且减法值与添加完全不同。 当字符串无法匹配时，这可能导致难以捉摸的错误。

我建议你改用循环移位和XOR。 这些操作很快，没有“浮点/双精度误差”

 uint32_t hash = 0; // This is not changed during cycle, so can be computed once before search. int rols = str_len & 31; 

添加哈希：

 hash = ((hash << 1) | (hash >> 31)) ^ ch; 

从哈希中删除：

 uint32_t x = ch; x = (x << rols) | (x >> (32 - rols)); hash ^= x; 

重要提示：添加后需要应用删除。