Java: Rabin–Karp with O(m + n) time


  • 1
    F
    public int strStr(String haystack, String needle) {
        if (needle == null || needle.length() == 0) return 0;
        if (haystack == null || haystack.length() == 0 || haystack.length() < needle.length()) return -1;
        
        long code = 0, res = 0;
        char c;
        int cur, len = needle.length();
         
        for (int i = 0; i < len; i++) {
            c = needle.charAt(i);
            cur = c - (c >= 'A' && c <= 'Z' ? 'A' : 'a');
            code = code * 52 + cur;
        }
        
       for (int i = 0; i < len; i++) {
            c = haystack.charAt(i);
            cur = c - (c >= 'A' && c <= 'Z' ? 'A' : 'a');
            res = res * 52 + cur;
        }
        
        if (res == code) return 0;
        
        for (int i = len; i < haystack.length(); i++) {
            c = haystack.charAt(i - len);
            cur = c - (c >= 'A' && c <= 'Z' ? 'A' : 'a');
            res = res - cur * (long) Math.pow(52, len - 1);
            
            c = haystack.charAt(i);
            cur = c - (c >= 'A' && c <= 'Z' ? 'A' : 'a');
            res = res * 52 + cur;
            
            if (res == code) return i - len + 1;
        }
        
        return -1;
    }

Log in to reply
 

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