Using rolling hash algorithm with complexity O(n), but fail the test when string gets longer


  • 0
    H
      public class Solution {
    public int strStr(String haystack, String needle) {
             if(haystack == null || needle == null) return -1;
        if(needle.length() > haystack.length()) return -1;
        if (haystack.length() == 0) return needle.length()==0? 0:-1;
        long needleValue = hashFun(needle);
        long haystackValue = hashFun(haystack.substring(0,needle.length()));
        if (needleValue == haystackValue) return 0;
    
        for(int i = 1; haystack.length() - i >= needle.length(); i++){
           haystackValue = haystackValue / 29 - haystack.charAt(i -1) / 29 + (long)haystack.charAt(i + needle.length() - 1) * (long)Math.pow(29, needle.length()-1);
            if (haystackValue == needleValue){
                return i;
            }
        }
    
        return -1;
    
    }
    
       public static long hashFun(String str){
        long res = 0;
        for(int i = 0; i < str.length(); i++){
            res += (int)str.charAt(i) * Math.pow(29,i);
        }
        return res;
    }
    

    }

    I am trying to implement the rolling hash algo, and the idea is pretty simple. But it seems that when the test string gets longer, the hash value gets overflowed, thus fail the test. Can anyone help me to fix this issue?
    Thanks!


  • 0
    M

    Why do you return i when the hashes are the same? You should check the actual string when the hashes are the same, because there might be different strings with same hash.

    You can use mod to keep your hash value in a specific range.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.