哈希生成器代码错误。它应该是
hash = (hash*257 + str[i]) % MOD;
并取消注释old_hash = old_hash % MOD;
。还改变从以前生成新哈希的方式
(old_hash - to_delete_char * pow(257, str_len-1)) % MOD;
看看你的代码。前两行非常好。循环中发生了什么。
首先,你要尽可能多地进行乘法运算。在我的方法中我使用霍纳方案计算哈希值,因为哈希值是多项式。
为什么它在没有模数和没有模数时都有效。我认为这是一个巧合,因为您溢出了 8 个字符的整数 (log(2^64)/log(257) = 8)。
现在删除字符有什么问题。to_delete_char * pow(257, str_len);
应该to_delete_char * pow(257, str_len-1);
索引应该从 0 而不是 1 开始以匹配您的生成器。
EDIT:我认为问题出在 pow 函数上。正如我上面所写,它只溢出了 8 个字符。在您的示例中,您有 10 个,因此它无法工作。
EDIT:事实证明,添加和删除字符必须作为一项操作完成。可能是由于等价物但我不确定。
#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;
}