# Java and Python solution using KMP with O(m + n) time complexity

• The time complexity for this solution should be O(m + n). First of all, we generate the "next" array to show any possible duplicates of prefix and postfix within needle. Then we go through haystack. Every time we see a bad match, move j to next[j] and keep i in current position; otherwise, move both of them to next position.
Python version:

``````def strStr(self, haystack, needle):
if haystack == None or needle == None:
return -1
#generate next array, need O(n) time
i, j, m, n = -1, 0, len(haystack), len(needle)
next = [-1] * n
while j < n - 1:
#needle[k] stands for prefix, neelde[j] stands for postfix
if i == -1 or needle[i] == needle[j]:
i, j = i + 1, j + 1
next[j] = i
else:
i = next[i]
print i,j,next[i],next[j]
#check through the haystack using next, need O(m) time
i = j = 0
while i < m and j < n:
if j == -1 or haystack[i] == needle[j]:
i, j = i + 1, j + 1
else:
j = next[j]
if j == n:
return i - j
return -1
``````

Java version:

``````public int strStr(String haystack, String needle){
if (haystack == null || needle == null)
return -1;
//generate next array, need O(n) time
int i = -1, j = 0, m = haystack.length(), n = needle.length();
int[] next = new int[n];
if (next.length > 0)
next[0] = -1;
while (j < n - 1) {
if (i == -1 || needle.charAt(i) == needle.charAt(j))
next[++j] = ++i;
else
i = next[i];
}
//check through the haystack using next, need O(m) time
i = 0; j = 0;
while (i < m && j < n) {
if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
}
else
j = next[j];
}
if (j == n)
return i - j;
return -1;
}``````

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