c/c++语言开发共享在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("%llun", rolling_hash("TestString")); printf("%llun", 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%llun", old); return 0; } 

只要我不引入任何余数操作，上面的代码就可以完美地运行; 一旦我取消注释我的%操作，事情就会崩溃，我从滚动哈希值的变化得到的答案将不会等于第二次打印所打印的答案。

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

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

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

 #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 

 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;