# KMP Algorithm in Python

• Here attached is my python Solution using KMP Algorithm.
The main idea is that we use the pattern inside the Pattern String, so that once we encounter a 'miss match', we can skip several bits to shorten the searching range. In Brute-Force algorithm, each time we will just switch to the next bit and start to compare from the very beginning.

It consists of two parts:

1. getNext():
Given a Pattern String "abdyab", we can get next = [-1, 0, 0, 0, 0, 1];
Let me show you a simple way to get next Array:
Pattern: "a b d y a b"
First: "0 0 0 0 1 2"
SubString that begins from the beginning to 'a' has no match of prefix and suffix, so we get 0;
Same as 'b' , 'd', y', till 'a'.
Now you can see the first 'a' (prefix) matches this 'a'(suffix), and the matched length is 1, So we get 1;
You can go all the way to the end.
Then, do a little trick: Right shift by one bit and put '-1' on the first element.
Thus, you got '-1, 0, 0, 0, 0, 1'

2. Start searching using the principle shown in the main idea.

Code and have fun:)

``````class Solution(object):
def strStr(self, haystack, needle):
if not needle:
return 0
length_hay = len(haystack)
length_needle = len(needle)
next = self.getNext(needle)
i = 0
j = 0
while i < length_hay:
if j == -1 or needle[j] == haystack[i]:
j += 1
i += 1
if j == length_needle:
return i - j
else:
j = next[j]
return -1

def getNext(self, needle):
next = []
next.append(-1)
length = len(needle)
j = 0
k = -1
while j < length - 1:
if k == -1 or needle[j] == needle[k]:
j += 1
k += 1
next.append(k)
else:
k = next[k]
return next
``````

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