# Knuth-Morris-Pratt Search Algorithm 2 Python

I tried again to implement the algorithm. Just need someone to check my work. I hope I didn't miss anything but my long work hours recently have been pretty taxing on my brain so I honestly wouldn't be surprised if I messed up somehow.

def KMP_table(wrd):
#example: B A A B D C B A A A C A B -> [-1, 0, 0, -1, 1, 2, -1, 0, 0, 0, 4, 5, -1]
table = []
position, candidate = 0, 0
while position < len(wrd):
if wrd[candidate] == wrd[position]:
table.append(-1)
candidate += (position - candidate)
elif wrd[position] == wrd[position - candidate] or candidate == 0:
table.append(0)
else:
table.append(position - candidate)
position += 1

return table

def KMP_search(wrd, str):

if not wrd or not str:
raise ValueError("Empty lists")

w, s = 0, 0
lenWrd, lenStr = len(wrd), len(str)
wrdPos = []

table = KMP_table(wrd)
while (s + lenWrd-1) < lenStr:
if wrd[w] == str[w + s]:
if w == lenWrd - 1:
wrdPos.append(s)
s += 1
w = 0
else:
w += 1
else:
if table[w] > 0:
s += (w - table[w])
elif w == 0:
s += 1
else:
s += w
w = 0

return wrdPos

# naming

The name of a variable is part of the documentation of your code. Try to use meaningful names, that don't shadow built-ins.

• wrd: sub (as in str.find)
• str: whole
• w: sub_index
• s: whole_index

# Generators

Instead of filling a list and returning that list, I prefer to work with generators in almost every case. If getting the result in a collection afterwards is very simple

# Looping

in KMP_table you are essentially looping by index (position). Instead, loop over the word and enumerate

# small things

• candidate += (position - candidate) is essentially candidate = position
• lenWrd is used twice, lenStr is used once, so they an be inline

# result

def KMP_table(whole):
# example: B A A B D C B A A A C A B -> [-1, 0, 0, -1, 1, 2, -1, 0, 0, 0, 4, 5, -1]
candidate = 0
for position, wrd_position in enumerate(whole):
diff = position - candidate
if whole[candidate] == wrd_position:
yield -1
candidate = position
elif wrd_position == whole[diff] or candidate == 0:
yield 0
else:
yield diff

def KMP_search(word, sub):
if not word or not sub:
raise ValueError("Empty lists")

word_index, sub_index = 0, 0
table = tuple(KMP_table(word))
while (sub_index + len(word) - 1) < len(sub):
if word[word_index] == sub[word_index + sub_index]:
if word_index == len(word) - 1:
yield sub_index
sub_index += 1
word_index = 0
else:
word_index += 1
else:
if table[word_index] > 0:
sub_index += (word_index - table[word_index])
elif word_index == 0:
sub_index += 1
else:
sub_index += word_index
word_index = 0

tuple(KMP_search('aba', 'aaababa'))
(2, 4)