# Rabin-Karp O(n + m) Java solution

• ``````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;
}
}
``````

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