I finally think I've implemented the Knuth–Morris–Pratt string search algorithm correctly, now time for that lovely criticism that causes me to learn! The code doesn't look all that pretty however it does work as far as I've tested. All of what I gathered on this algorithm comes from the Wikipedia page for it. I would appreciate some feedback and suggestions on improvements/errors. Did I hit the mark? Or did I miss the point? Should I employ other sources for my research?
'''
KMP Algorithm
**Searches for all occurrences of a word w[] in main string s[]
@author: Anonymous3.1415
'''
def KMP_filltable(pattern):
position = 2
candidate = 0
length_pat = len(pattern)
table = [0]*len(pattern)
table[0] = -1
while position < length_pat:
if pattern[position - 1] == pattern[candidate]:
position += 1
candidate += 1
table[position - 1] = candidate
elif candidate > 0:
candidate = table[candidate]
else:
table[position] = 0
position += 1
return table
def KMP_search(pattern, lst):
positions = []
i, j = 0, 0
length_lst, length_pat = len(lst), len(pattern)
table = KMP_filltable(pattern)
while i < length_lst:
if pattern[j] == lst[i + j]:
j += 1
if j == length_pat:
positions.append(i)
i += j
j = 0
elif table[j] > 0:
j = table[j]
i += j
else:
i += (j + 1)
j = 0
return positions