# May I know why this python KMP solution timeout?

• Here is my KMP solution in Python. It passed 73/74 test cases but failed for the long 'aaaa...' one because of a timeout.

``````class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
if not needle:
return 0

NEXT = get_next_array(needle)
len_y = len(haystack)
len_n = len(needle)
n_index = 0
i = 0
while i < len_y and n_index < len_n:

if haystack[i] == needle[n_index]:
n_index += 1
i += 1
elif n_index > 0:
n_index = NEXT[n_index - 1] + 1
else:
i += 1

return i - len_n if n_index == len_n else -1

def get_next(N, j):
if j == 0:
return -1
i = get_next(N, j-1)
while (N[i+1] != N[j] and i >= 0):
i = get_next(N, i)

return i + 1 if N[i+1] == N[j] else -1

def get_next_array(s):
r = [0] * len(s)
for i, c in enumerate(s):
r[i] = get_next(s, i)
return r
``````

Appreciate if anyone could help to point out where I missed.

Thanks a log guys!

• Found the reason finally. My get_next_array function is O(M*N) so that it timed out during generate the next array.

Thanks to @gajni 's solution https://discuss.leetcode.com/topic/67730/o-m-n-and-o-mn-solutions which enlighten me.

Here is the modified solution that accepted.

``````class Solution:
# @param {string} haystack
# @param {string} needle
# @return {integer}
def strStr(self, haystack, needle):
if not needle:
return 0

NEXT = get_next_array_v2(needle)
len_y = len(haystack)
len_n = len(needle)
n_index = 0
i = 0
while i < len_y:
c = haystack[i]
if c == needle[n_index]:
n_index += 1
i += 1

if n_index == len_n:
return i - len_n

if i < len_y and haystack[i] != needle[n_index]:
if n_index == 0:
i += 1
else:
n_index = NEXT[n_index - 1] + 1

return -1

def get_next_array_v2(s):
len_s = len(s)
r = [-1] * len_s
pre_i, suf_i = 0, 1
while suf_i < len_s:
if s[pre_i] == s[suf_i]:
r[suf_i] = pre_i
pre_i += 1
suf_i += 1
elif pre_i:
pre_i = r[pre_i - 1] + 1
else:
r[suf_i] = -1
suf_i += 1
return r
``````

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