如果我们忽略取模部分并让 hash int/long 溢出，rabin-karp 字符串搜索算法是否仍然正确？
Is rabin-karp string search algorithm still correct if we neglect the modulo part and let hash int/long overflow?
我有一个疑问：如果让rolling hash溢出，会不会影响Rabin-Karp算法的正确性？能否举个具体例子，溢出确实会影响正确性？
这类似于相同的字符串，例如当您直接从“abcd”或“eabcd”计算时，“abcd”将给出不同的哈希值 (hash("eabc") - hash("e") * R^3) * R + hash("d")
hash("abcd") != (hash("eabc") - hash("e") * R^3) * R + hash("d")
如果我们允许 int/long 溢出
我认为这不会影响算法的正确性，因为两个相等的输入在提交给相同的函数时会 return 相同的输出。当滚动哈希添加和减去元素时，它不应该影响每个单独的结果，即使它溢出。
在使用无符号整数进行滚动散列的情况下，无符号溢出等效于 2^32 或 2^64 的模数，具体取决于无符号类型的大小。所以你的问题的答案是肯定的，算法仍然是正确的。 （作为练习，想想为什么unsigned overflow会等同于modding？）
事实上，您会在许多快速实现中看到，它们不显式使用模运算，而是使用无符号溢出作为隐式模运算来提高速度；例如，请参阅 Charras 和 Lecroq 在 C 中的示例实现：https://www-igm.univ-mlv.fr/~lecroq/string/node5.html
仍然在伪代码演示中保留模运算，因为最好在演示算法时 显式 进行这样的运算，以便于理解和注意细节。
我有一个疑问：如果让rolling hash溢出，会不会影响Rabin-Karp算法的正确性？能否举个具体例子，溢出确实会影响正确性？
这类似于相同的字符串，例如当您直接从“abcd”或“eabcd”计算时，“abcd”将给出不同的哈希值 (hash("eabc") - hash("e") * R^3) * R + hash("d")
hash("abcd") != (hash("eabc") - hash("e") * R^3) * R + hash("d") 如果我们允许 int/long 溢出
我认为这不会影响算法的正确性，因为两个相等的输入在提交给相同的函数时会 return 相同的输出。当滚动哈希添加和减去元素时，它不应该影响每个单独的结果，即使它溢出。
在使用无符号整数进行滚动散列的情况下，无符号溢出等效于 2^32 或 2^64 的模数，具体取决于无符号类型的大小。所以你的问题的答案是肯定的，算法仍然是正确的。 （作为练习，想想为什么unsigned overflow会等同于modding？）
事实上，您会在许多快速实现中看到，它们不显式使用模运算，而是使用无符号溢出作为隐式模运算来提高速度；例如，请参阅 Charras 和 Lecroq 在 C 中的示例实现：https://www-igm.univ-mlv.fr/~lecroq/string/node5.html
仍然在伪代码演示中保留模运算，因为最好在演示算法时 显式 进行这样的运算，以便于理解和注意细节。