概括：有没有办法做到这一点？这就是我的意思：假设我有一个无符号整数数字。然后我将其相乘几次（并且出现溢出，这是预期的）。那么是否可以“恢复”原来的值呢？
详细信息：
这全都是关于Rabin-Karp 滚动哈希 http://en.wikipedia.org/wiki/Rolling_hash。我需要做的是：我有一个长字符串的哈希值 - 例如：“abcd”。然后我得到了较短子字符串的哈希值 - 例如“cd”。如何使用两个给定的哈希值以 O(1) 计算“ab”哈希值？
我现在拥有的算法：
- 从“abcd”哈希中减去“cd”哈希（从多项式中删除最后一个元素）
- 将“abcd”哈希除以
p ^ len( "cd" ), where p是基数（素数）。
所以这是：
a * p ^ 3 + b * p ^ 2 + c * p ^ 1 + d * p ^ 0 - abcd
c * p ^ 1 + d * p ^ 0 - cd
ab gets:
(
( a * p ^ 3 + b * p ^ 2 + c * p ^ 1 + d * p ^ 0 ) -
( c * p ^ 1 + d * p ^ 0 )
)
/ ( p ^ 2 )
= a * p ^ 1 + b * p ^ 0
如果我没有溢出（如果p是小数）。但如果不是——它就不起作用。
有什么技巧或者什么吗？
附：这c++标签是因为数字溢出，因为它是特定的（并且与python、scheme或sth不同）
不知道溢出部分，但有一种方法可以恢复原始值。
中国剩余定理有很大帮助。我们打电话吧h = abcd - cd。 G 是值，h，没有溢出，G = h + k*2^32，假设溢出只是%2^32。因此ab = G / p^2.
G = h (mod 2^32)
G = 0 (mod p^2)
如果 p^2 和 2^32 互质。此页面位于中国剩余定理 http://mathworld.wolfram.com/ChineseRemainderTheorem.html， 给我们
G = h * b * p^2 (mod 2^32 * p^2)
Where b是 p^2 模 2^32 的模乘逆，b * p^2 = 1 (mod 2^32)。计算完之后G，简单地除以p^2找到ab.
我希望我没有犯任何错误...
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
