Java - Rabin Karp - Rolling Hash - 45ms but beats only 2.84% ?


  • 0

    Hi, I implemented Rabin-Karp with rolling hash function but I could only beat 2.84% of submissions and it took 45ms. Can anyone please explain why this solution worked worse than brute force?

    public class Solution {
        private static final int PRIME = 3;
        
        private int hash(char[] input, int len) {
            int hash = 0;
    
            for(int index=0; index<len; index++) {
                hash += input[index] *((int) Math.pow(PRIME, index));
            }
            
            return hash;
        }
        
        private int hash(int prevHash, char oldChar, char newChar, int len) {
            return ((prevHash - oldChar)/ PRIME + newChar * ((int) Math.pow(PRIME, len-1)));
        }
        
        private boolean checkCompare(char[] needleArray, char[] haystackArray, int beginIndex, int endIndex) {
            int counter = 0;
            while(beginIndex <= endIndex) {
                if(needleArray[counter] != haystackArray[beginIndex]) {
                    return false;
                }
                
                ++counter;
                ++beginIndex;
            }
            
            return true;
        }
        
        public int strStr(String haystack, String needle) {
            if(null == haystack || null == needle) {
                return -1;
            }
    
            int needleLen = needle.trim().length();
            int haystackLen = haystack.trim().length();
    
            if(haystackLen < needleLen) {
                return -1;
            }
            
            if(needleLen == 0) {
                return 0;
            }
            
            char[] needleArray = needle.trim().toCharArray();
            int needleHash = hash(needle.trim().toCharArray(), needleLen);
            
            char[] haystackArray = haystack.trim().toCharArray();
            int prevHash = hash(haystackArray, needleLen);
            
            if(checkCompare(needleArray, haystackArray, 0, needleLen-1)) {
                return 0;
            } else if(needleLen == haystackLen) {
                return -1;
            }
            
            for(int index=1; index + needleLen <= haystackLen; index++) {
                int newHash = hash(prevHash, haystackArray[index-1], haystackArray[index+needleLen-1], needleLen);
    
                if(needleHash == newHash && checkCompare(needleArray, haystackArray, index, index+needleLen-1)) {
                    return index;
                }
                
                prevHash = newHash;
            }
            
            return -1;
            
        }
    }
    

Log in to reply
 

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