Knuth-Morris-Pratt Search Algorithm 2 Python
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)