用Rolling hash写strStr时遇到了一个奇怪的问题，求解。

水逼一枚 发表于 2015-6-27 07:29
不好意思，我说反了，是第二个能AC，第一个TLE。只是比较好奇，感觉很诡异。

那就更诡异了(x_x)
还是转而琢磨琢磨kmp、sunday或者bm吧

楼主这种计算hash的方法确定不会溢出么？long的取值范围最大是2^63-1, 而29接近于2^5 = 32。那么就算target中所有字符的ascii码都是1，也只需要最多13个字符就能使得hash溢出（因为 (2^5)^13 > 2^63)。溢出以后的值会回卷，变为(hash+2^63) % 2^64 - 2^63也就是说，楼主代码的正确性，应当是建立在

"在长度为K
的所有可能的字符串的hash值的集合M中，取任意hash值H, 那么 (H+2^63) % 2^64 - 2^63)不会和该集合内的所有其他hash值的 (H'+2^63) % 2^64 - 2^63)值重复”。

这点如果不能证明的话，那么就很可能出现这种情况。就是两个字符串本来不相同，但是其中一个的hash值H没有回卷，而另一个hash值H'有回卷。回卷的那个数H'绕了一圈以后恰好又和H相等，这时候就会错误地判定二字符串相等了。

虽然很有可能上述情况并不会出现（base是个质数），但我觉得如果真的要用这种方法的话，还是需要严格证明为佳。