Rabin-Karp Javascript with hash


  • 0
    R

    Reference: http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html

    var strStr = function(haystack, needle) {
        if(needle.length > haystack.length) {
            return -1;
        }
        if(!needle){
            return 0;
        }
        var R = 256;
        var Q = 999991;
        var M = needle.length;
        var RM = 1;
        
        for(var a = 1; a <= M-1; a++) {
            RM = (R*RM)%Q;
        }
        var phash = hash(needle, M, Q, R);
        var hashy = hash(haystack, M, Q, R);
        if(phash === hashy) return 0;
        
        for(var i = 1; i+M-1 <= haystack.length-1; i++) {
            var nextHash = (hashy + Q - haystack.charCodeAt(i-1)*RM%Q) % Q;
            nextHash = (nextHash*R%Q+haystack.charCodeAt(i+M-1))%Q;
            if(nextHash === phash) {
                return i;
            }
            hashy = nextHash;
        }
        return -1;
    };
    
    var hash = function(str, len, Q, R) {
        var h = 0;
        for(var i = 0; i < len; i++) {
            h = (h*R+str.charCodeAt(i))%Q;
        }
        return h;
    };
    

  • 0
    P

    Correct me if i am wrong but there is a mistake in
    if(nextHash === phash) {
    return i;
    }
    When two hash functions are the same we also need to check equality of those two Strings character by character because of collision.


Log in to reply
 

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