# *Java* 2 solutions: KMP O(m+n) & brute force O(mn)

• #Brute Force#

``````public int strStr(String str, String pattern) {
int lenH = str.length(), len = pattern.length();
for(int i=0; i<=lenH-len; i++) {
if(pattern.equals(str.substring(i,i+len))) return i;
}
return -1;
}
``````

#KMP (based on my understanding of this video)#

``````public int strStr(String str, String pattern) {
char[] strs = str.toCharArray();
char[] patterns = pattern.toCharArray();
int L=strs.length, N=patterns.length, i=0, j=0; // i: str pointer, j: pattern pointer
if(N<1) return 0;
if(L<N) return -1;
int[] lps = lps(pattern); // get the array that stores the longest subarray whose prefix is also its suffix
while(i<L) {
if(strs[i]==patterns[j]) { // same value found, move both str and pattern pointers to their right
++i;
++j;
if(j==N) return i-N; // whole match found
}
else if(j>0) j = lps[j-1]; // move pattern pointer to a previous safe location
else ++i; // restart searching at next str pointer
}
return -1;
}

private int[] lps(String pattern) {
int j=0, i=1, L=pattern.length();
int[] res = new int[L];
char[] chars = pattern.toCharArray();
while(i<L) {
if(chars[i]==chars[j]) res[i++] = ++j;
else {
int temp = i-1;
while(temp>0) {
int prevLPS = res[temp];
if(chars[i]==chars[prevLPS]) {
res[i++] = prevLPS+1;
j = prevLPS;
break;
}
else temp = prevLPS-1;
}
if(temp<=0) {
res[i++] = 0;
j = 0;
}
}
}
return res;
}
``````

Just for fun, here is a recursive one but has StackOverflowError:

``````public int strStr(String str, String pattern) {
return strStr(str, str.length(), 0, pattern, pattern.length(), 0);
}
private int strStr(String str, int L, int i, String pattern, int N, int j) {
if(j==N) return i-N;
if(i>=L) return -1;
if(str.charAt(i)!=pattern.charAt(j)) ++j;
else j = 0;
return strStr(str, L, ++i, pattern, N, j);
}
``````

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