Knuth–Morris–Pratt string search algorithm

Question

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

Answer 1

This code does not work. In some cases it fails to find the pattern:

>>> KMP_search('ab', 'aab')
[]

In other cases it raises an exception:

>>> KMP_search('ab', 'ba')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "cr190837.py", line 39, in KMP_search
    if pattern[j] == lst[i + j]:
IndexError: string index out of range

How could you have found these problems? Well, by testing the code thoroughly. One way to do this is to use random test case generation. The idea behind randomized testing is that it can test a much larger range of inputs than you could ever enter by hand, and it can test parts of the space of inputs that would not be reached by systematic test case generation.

So one idea for a random test case would be to generate a random string of length k:

haystack = ''.join(random.choices('abc', k=k))

(Here I'm using random.choices which was new in Python 3.6. If you're on an earlier version of Python, you could use a loop like random.choice('abc') for _ in range(k).)

Then pick a random substring:

start, stop = sorted(random.sample(range(k + 1), 2))
needle = haystack[start:stop]

Run KMP_search(needle, haystack) and check that the results are correct, for example by comparing with Python's built-in str.find.

This can all be packaged together into a unit test using the unittest module:

import random
import unittest

class TestKMPSearch(unittest.TestCase):
    "Unit tests for KMP_search."

    def test_positive(self):
        for k in range(1, 100):
            # Generate a random test case with k characters.
            haystack = ''.join(random.choices('abc', k=k))
            start, stop = sorted(random.sample(range(k + 1), 2))
            needle = haystack[start:stop]

            # Use Python's built-in str.find to compute the expected result.
            expected = []
            index = -1
            while True:
                index = haystack.find(needle, index + 1)
                if index == -1:
                    break
                expected.append(index)

            # Compare with the actual result.
            found = KMP_search(needle, haystack)
            self.assertEqual(found, expected,
                             "KMP_search({!r}, {!r})".format(needle, haystack))

(I called the method test_positive because the test cases are positive in the sense that the needle is found in the haystack. For really thorough testing you ought to generate some negative test cases too, ones in which the needle is not found. But this is enough to find some errors.)

Now if you run the unit tests you'll (most likely) get a failure like this:

$ python -munittest cr190837.py
F
======================================================================
FAIL: test_positive (cr190837.TestKMPSearch)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "cr190837.py", line 79, in test_positive
    "KMP_search({!r}, {!r})".format(needle, haystack))
AssertionError: Lists differ: [] != [3]

Second list contains 1 additional elements.
First extra element 0:
3

- []
+ [3]
?  +
 : KMP_search('bac', 'ccbbac')

----------------------------------------------------------------------
Ran 1 test in 0.001s

FAILED (failures=1)