Accepted Java code. Simple Rabin–Karp implementation.


  • 2
    P
    private static final int BASE = 31;
    
    public int strStr(String haystack, String needle) {
    	char[] H = haystack.toCharArray();
    	char[] N = needle.toCharArray();
    	int len = N.length;
    	
    	// Edge cases
    	if (len == 0) return 0;
    	if (H.length < len) return -1;
    	
    	// Base
        int[] base = new int[len];
        base[0] = 1;
        for (int i=1; i<len; i++) base[i] = base[i-1] * BASE;
        
        // 'needle' hash
        int hash = 0;
        for (int i=0; i<len; i++) hash += N[i]*base[len-1-i];
        
        // 'haystack' start hash
        int h = 0;
        for (int i=0; i<len; i++) h += H[i] * base[len-1-i];
        if (h == hash) return 0;
        
        // Search
        for (int i=len; i < H.length; i++) {
        	h = BASE * (h - (H[i-len] * base[len-1])) + H[i];
        	if (h == hash) {
        		// strickt compare
        		for (int j=0; j<len; j++) {
        			if (H[i-j] != N[len-1-j]) continue;
        		}
        		return i-len+1;
        	}
        }
        
        return -1;
    }

  • 0
    Q
    This post is deleted!

  • 0
    Q

    Your code is very elegant and clean.
    Although your code is passed OJ, I think there are some problems in your code. In the double loop, your code: if (H[i-j] != N[len-1-j]) continue, I think it should be if (H[i-j] != N[len-1-j]) break;

    you should add the condition to return the value "if (j == len) return i-len+1;".

    "if (h == hash) return 0;" also should be changed to "if (h == hash && haystack.substring(0, len). equals(needle)) return 0;"


  • -1
    S

    I used Java's String.hashCode() method to implement Rabin Karp, here's my solution:

        public int strStr(String str, String substr) {
            int i, n = str.length(), m = substr.length();;
            int hashPattern = substr.hashCode();
            for (i = 0; i < n - m + 1; i ++ ) {
                int hs = str.substring(i, i + m).hashCode();
                if (hs == hashPattern) return i;
            }
            return -1;
        }

  • 0

    That's really not Rabin-Karp. You missed its entire point. And actually made it less efficient than a naive search. And it doesn't even work, for example you fail the input "baaaaacbaacbb", "abcacaaaabaac".


  • 0
    S

    You're right as it doesn't use rolling hash so it recomputes the hash of the substring at each iteration. The reason your test case doesn't work is because I used Java's native hashCode() function, it was sufficient for leetcode's test cases. Normally you would want to implement a much better hash function.


  • 0

    No, the reason it fails is that you're doing it wrong. If the current substring's hash matches, then you ought to also check the current substring itself.


  • 0
    B

    What is the Base=31 for?


Log in to reply
 

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