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

先上正确的代码：

1. public static int strStr(String source, String target) {
   
2.         if (target.length() > source.length())
   
3.             return -1;
   
4.         int base = 29;
   
5.         long tmpBase = 1;
   
6.         long targetHash = 0;
   
7.         long sourceHash = 0;
   
8.         for (int i = target.length()-1; i >= 0; i--) {
   
9.             tmpBase *= base;
   
10.             targetHash = targetHash * base + (int)target.charAt(i);            
    
11.             sourceHash = sourceHash * base + (int)source.charAt(i);
    
12.         }
    
13.         tmpBase /= base;
    
14.         
    
15.         if (targetHash == sourceHash)
    
16.             return 0;
    
17.         
    
18.         System.out.println(targetHash);
    
19.         for (int i = target.length(); i < source.length(); i++) {            
    
20.             sourceHash = (sourceHash-(int)source.charAt(i-target.length()))/base + source.charAt(i)*tmpBase;
    
21.             System.out.println(sourceHash);
    
22.             if (targetHash == sourceHash)
    
23.                 return i - target.length()+1;
    
24.         }
    
25.         return -1;
    
26.     }

复制代码

计算rolling hash值得时候这样写是对的：
sourceHash = (sourceHash-(int)source.charAt(i-target.length()))/base + source.charAt(i)*tmpBase;
但如果我写成sourceHash = sourceHash/base + source.charAt(i)*tmpBase; 结果就不对，我觉得二者应该等价啊？ 感觉是java中数值计算的问题，请教大家了！

kurtwang 发表于 2015-5-6 01:38
上面你提到的两个公式相同的成立的前提是你的base是要比c0....cn都要大才行，比如'a'是97,但你的base是29 ...

1. public class Solution {
   
2.     public int strStr(String haystack, String needle) {
   
3.         if( haystack == null || needle == null ){
   
4.             return -1;
   
5.         }
   
6.         if( needle.length() == 0 ){
   
7.             return 0;
   
8.         }
   
9.         if( haystack.length() == 0){
   
10.             return -1;
    
11.         }
    
12. 
    
13.         int haystackLen = haystack.length();
    
14.         int needleLen = needle.length();
    
15.    
    
16.         for(int i = 0; i < haystackLen; i++){
    
17.             int j;
    
18.             for(j = 0; (i + j) < haystackLen && j < needleLen; j++){
    
19.                 if( haystack.charAt(i + j) != needle.charAt(j) ){
    
20.                     break;
    
21.                 }
    
22.             }
    
23.             if( j == needleLen ){
    
24.                 return i;
    
25.             }
    
26.         }
    
27.        return -1;
    
28.     }
    
29. }
    

复制代码

1. public class Solution {
   
2.     public int strStr(String haystack, String needle) {
   
3.         if( haystack == null || needle == null ){
   
4.             return -1;
   
5.         }
   
6.         if( needle.length() == 0 ){
   
7.             return 0;
   
8.         }
   
9.         if( haystack.length() == 0){
   
10.             return -1;
    
11.         }
    
12. 
    
13.         int haystackLen = haystack.length();
    
14.         int needleLen = needle.length();
    
15.    
    
16.         for(int i = 0; i < haystackLen; i++){
    
17.             int tmp = i;
    
18.             int j;
    
19.             for(j = 0; (tmp + j) < haystackLen && j < needleLen; j++){
    
20.                 if( haystack.charAt(tmp + j) != needle.charAt(j) ){
    
21.                     break;
    
22.                 }
    
23.             }
    
24.             if( j == needleLen ){
    
25.                 return i;
    
26.             }
    
27.         }
    
28.        return -1;
    
29.     }
    
30. }
    

复制代码

请问一下，上面两个程序首先我知道他们都有个问题就是外层for循环的边界还可以进一步缩小。我的疑问是，只看上面两个程序的话，为什么第一个可以AC，第二个会TLE呢？谢谢。

楼主这种计算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是个质数），但我觉得如果真的要用这种方法的话，还是需要严格证明为佳。

kellogg 发表于 2015-5-6 01:32
计算rolling hash的公式：Hash = c0*base^0+c1*base^1+c3*base^3+c4*base^4 那么计算下一组Hash的时候只 ...

上面你提到的两个公式相同的成立的前提是你的base是要比c0....cn都要大才行，比如'a'是97,但你的base是29,如果你不减去97，直接除的话，就会多出来3，如果把base设成(int)'z'+1应该两个就一样了，话说楼主是poly的？

这两个明显不等价啊。。
6/2和(6-1)/2结果不一样

kurtwang 发表于 2015-5-6 00:02
这两个明显不等价啊。。
6/2和(6-1)/2结果不一样

计算rolling hash的公式：Hash = c0*base^0+c1*base^1+c3*base^3+c4*base^4 那么计算下一组Hash的时候只需要Hash/base+c5*base^4就可以了，只要base的值大于c能取到的最大值

kurtwang 发表于 2015-5-6 01:38
上面你提到的两个公式相同的成立的前提是你的base是要比c0....cn都要大才行，比如'a'是97,但你的base是29 ...

你说得对，我把ascii码记错了。。

kurtwang 发表于 2015-5-6 01:38
上面你提到的两个公式相同的成立的前提是你的base是要比c0....cn都要大才行，比如'a'是97,但你的base是29 ...

恩 poly的

kellogg 发表于 2015-5-6 01:50
恩 poly的

请问一下楼主，为什么要想到用这个方法来做这个题呢？

水逼一枚 发表于 2015-6-27 00:26
请问一下，上面两个程序首先我知道他们都有个问题就是外层for循环的边界还可以进一步缩小。我的疑问是， ...

两个都是brute-force，而且第二个的那个tmp用的毫无意义，感觉没必要去琢磨吧。。

zhuli19901106 发表于 2015-6-27 07:13
两个都是brute-force，而且第二个的那个tmp用的毫无意义，感觉没必要去琢磨吧。。

不好意思，我说反了，是第二个能AC，第一个TLE。只是比较好奇，感觉很诡异。