# KMP in Python, but very slow :(

• Guys, I tried to wrote the KMP algorithm, but it's very slow. Anyone can do me a favor to figure out where the problem is ? Thanks!

``````class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
# Define next array
def next_arr(needle):
next = [-1]*len(needle)
for i in range(1, len(needle)):
j = next[i-1]
while j>=0 and needle[j+1] != needle[i]:
j = next[j]
next[i] = j+1 if needle[j+1] == needle[i] else j
return next

# Find the index of substr
def sub_str(haystack, needle, next):
j = -1
for i in range(-1, len(haystack)-1):
while j > -1 and haystack[i+1] != needle[j+1]:
j = next[j]
j = j+1 if haystack[i+1] == needle[j+1] else j
if j == len(needle)-1:
return i+1-j
return -1

if len(needle) > len(haystack):
return -1
if not needle:
return 0
next = next_arr(needle)
return sub_str(haystack, needle, next)

``````

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