Rabin-Karp O(n + m) Java solution


  • 0
    P
    public class Solution {
        public int strStr(String txt, String pat) {
    		int m = pat.length(), n = txt.length();
    		if(m > n){
    		    return -1;
    		}
    		long hP = 0, hT = 0, x = 31;
    		long y = 1, p = 10000000007L;
    
    		for (int i = 0; i < pat.length(); i++) {
    			y = y % p * x % p;
    		}
    
    		hT = polyHash(txt.substring(0, pat.length()), p);
    		hP = polyHash(pat, p);
    
    		for (int i = 0; i <= txt.length() - pat.length(); i++) {
    			if (hT == hP) {
    				if (areEqual(txt, pat, i)) {
                        return i;
    				}
    			}
    			if (i + pat.length() < txt.length()) {
    				hT = ((x * hT + txt.charAt(i + pat.length()) - (txt.charAt(i) * y)) % p + p) % p;
    			}
    		} 
    		return -1;
        }
    
    	public boolean areEqual(String s1, String s2, int i) {
    		int j;
    		for (j = 0; j < s2.length(); j++) {
    			if (s1.charAt(i + j) != s2.charAt(j)) {
    				return false;
    			}
    		}
    		return true;
    	}
    
    	public long polyHash(String s, long p) {
    		long h = 0;
    		for (int i = 0; i < s.length(); i++) {
    			h = (h * x + (int) s.charAt(i)) % p;
    		}
    		return h;
    	}
    }
    

Log in to reply
 

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