O(m+n) and O(mn) solutions

• Solution 1: O(m+n) KMP pattern matching

`````` public int strStr(String haystack, String needle) {
if(haystack == null || needle == null || needle.length() > haystack.length()) return -1;

int[] parr = kmpPreprocess(needle);
int i = 0, j = 0;
while(i < haystack.length() && j < needle.length()) {
if(haystack.charAt(i) == needle.charAt(j)) {
i++; j++;
} else if(j > 0) {
j = parr[j - 1];
} else {
i++;
}
}
return j == needle.length() ? i - j : -1;
}

private int[] kmpPreprocess(String pattern) {
int i = 1, j = 0;
int[] res = new int[pattern.length()];
while(i < pattern.length()) {
if(pattern.charAt(i) == pattern.charAt(j)) {
res[i] = j+1;
i++; j++;
} else if (j > 0) {
j = res[j-1];
} else {
res[i] = 0;
i++;
}
}
return res;
}
``````
• If you want to understand KMP, watch the video.

• KMP finds the pattern in a most efficient way. If the use cases require running multiple patterns then Rabin Karp algorithm may be useful.

Solution 2: O(mn) Brute Force

`````` public int strStr(String haystack, String needle) {
if(haystack == null || needle == null || needle.length() > haystack.length()) return -1;

int len = haystack.length(), i = 0, j = 0, pos = 0;
while(i < len && j < needle.length()) {
if(haystack.charAt(i++) == needle.charAt(j)) {
j++;
} else {
i = i - j;
j = 0;
pos = i;
}
}
return j == needle.length()? pos : -1;
}
``````

• Thanks for sharing！

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