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 -&gt; [-1, 0, 0, -1, 1, 2, -1, 0, 0, 0, 4, 5, -1]
    table = []
    position, candidate = 0, 0
    while position &lt; 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) &lt; 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] &gt; 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 -&gt; [-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) &lt; 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] &gt; 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)