一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 630|回复: 11
收起左侧

[Leetcode] 用Rolling hash写strStr时遇到了一个奇怪的问题,求解。

[复制链接] |试试Instant~ |关注本帖
kellogg 发表于 2015-5-5 23:05:50 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
先上正确的代码:
  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 00:02:48 | 显示全部楼层
这两个明显不等价啊。。
6/2和(6-1)/2结果不一样
回复 支持 反对

使用道具 举报

 楼主| kellogg 发表于 2015-5-6 01:32:01 | 显示全部楼层
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:46 | 显示全部楼层
本帖最后由 kurtwang 于 2015-5-6 01:45 编辑
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的?
回复 支持 反对

使用道具 举报

 楼主| kellogg 发表于 2015-5-6 01:45:59 | 显示全部楼层
kurtwang 发表于 2015-5-6 01:38
上面你提到的两个公式相同的成立的前提是你的base是要比c0....cn都要大才行,比如'a'是97,但你的base是29 ...

你说得对,我把ascii码记错了。。
回复 支持 反对

使用道具 举报

 楼主| kellogg 发表于 2015-5-6 01:50:17 | 显示全部楼层
kurtwang 发表于 2015-5-6 01:38
上面你提到的两个公式相同的成立的前提是你的base是要比c0....cn都要大才行,比如'a'是97,但你的base是29 ...

恩 poly的
回复 支持 反对

使用道具 举报

DownToEarth 发表于 2015-6-27 00:19:18 | 显示全部楼层

请问一下楼主,为什么要想到用这个方法来做这个题呢?
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-6-27 00:26:54 | 显示全部楼层
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.         int haystackLen = haystack.length();
  13.         int needleLen = needle.length();
  14.    
  15.         for(int i = 0; i < haystackLen; i++){
  16.             int j;
  17.             for(j = 0; (i + j) < haystackLen && j < needleLen; j++){
  18.                 if( haystack.charAt(i + j) != needle.charAt(j) ){
  19.                     break;
  20.                 }
  21.             }
  22.             if( j == needleLen ){
  23.                 return i;
  24.             }
  25.         }
  26.        return -1;
  27.     }
  28. }
复制代码
  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.         int haystackLen = haystack.length();
  13.         int needleLen = needle.length();
  14.    
  15.         for(int i = 0; i < haystackLen; i++){
  16.             int tmp = i;
  17.             int j;
  18.             for(j = 0; (tmp + j) < haystackLen && j < needleLen; j++){
  19.                 if( haystack.charAt(tmp + j) != needle.charAt(j) ){
  20.                     break;
  21.                 }
  22.             }
  23.             if( j == needleLen ){
  24.                 return i;
  25.             }
  26.         }
  27.        return -1;
  28.     }
  29. }
复制代码
请问一下,上面两个程序首先我知道他们都有个问题就是外层for循环的边界还可以进一步缩小。我的疑问是,只看上面两个程序的话,为什么第一个可以AC,第二个会TLE呢?谢谢。
回复 支持 反对

使用道具 举报

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

两个都是brute-force,而且第二个的那个tmp用的毫无意义,感觉没必要去琢磨吧。。
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-6-27 07:29:21 | 显示全部楼层
zhuli19901106 发表于 2015-6-27 07:13
两个都是brute-force,而且第二个的那个tmp用的毫无意义,感觉没必要去琢磨吧。。

不好意思,我说反了,是第二个能AC,第一个TLE。只是比较好奇,感觉很诡异。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-6-27 07:51:20 | 显示全部楼层
水逼一枚 发表于 2015-6-27 07:29
不好意思,我说反了,是第二个能AC,第一个TLE。只是比较好奇,感觉很诡异。

那就更诡异了(x_x)
还是转而琢磨琢磨kmp、sunday或者bm吧
回复 支持 反对

使用道具 举报

stellari 发表于 2015-6-27 10:40:14 | 显示全部楼层
楼主这种计算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是个质数),但我觉得如果真的要用这种方法的话,还是需要严格证明为佳。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 23:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表