string - 模数可以分布吗？

Question

它可以在数学中，但我在研究 Rabin-Carp 字符串搜索算法时遇到了这个问题。他们使用的哈希函数（来源：维基百科：https ://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm#Hash_function_used ）是这样的：

[(104 × 256 ) % 101  + 105] % 101  =  65

这比删除内部 mod 运算符以便您只有一个在外部更好吗？这样：

[104 × 256  + 105] % 101

据我所知，它应该给出相同的结果，而且模组通常是昂贵的操作，所以拥有一个不是更好吗？

我唯一能想到的是对溢出的担忧，但如果是这样的话，乘法也会被类似地分开，如下所示：

(104 % 101 × 256 % 101 ) % 101  + 105] % 101  =  65

标签： stringmathhash

Answer 1

当您实施一个公式时，通常您会尝试拥有相同的前景。假设公式如下所示：

[(x × y) % z + t] % w

在我们的例子中，z 和 w 具有相同的值，但它们可能不同。如果您简化公式以匹配您的情况，那么将来，如果 z 和 w 之间的差异开始蔓延，那么您将很难找出代码的含义。然而，如果 z 和 w 是纠缠的，并且保证它们将来也会纠缠，那么你可以考虑这种简化。但是，您在这样做时也需要小心，因为如果 x 和 y 相当大，那么在某些情况下添加 t 时可能会出现一些数字溢出问题。此外，如果 t 非常大，您可能会遇到数字溢出问题。

至于你的问题，

[a % b + c] % b

相当于

[a + c] % b

数学上。但在实际代码中，可能会有一些细微差别证明代码看似多余。