# Naive implementation of KMP algorithm

After reading this answer to the question "High execution time to count overlapping substrings", I decided to implement the suggested Knuth-Morris-Pratt (KMP) algorithm. I used the pseudo-code listed on Wikipedia for the functions kmp_table and kmp_search.

However, when running it on some corner-cases, I have observed that it is a lot slower than the standard str.find, which apparently uses a modified Boyer-Moore-Horspool algorithm and should thus have worse worst-case performance.

The specific case I looked at is:

\$ ipython -i kmp.py
In [1]: text = "A"*1000000 + "B"
In [2]: word = "A"*100 + "B"
In [3]: %timeit kmp_search(text, word)
1 loop, best of 3: 410 ms per loop
In [4}: %timeit text.find(word)
1000 loops, best of 3: 703 µs per loop


So the difference is about a factor 1000 for this input. This is probably due to the fact that the native one is written in C and this is written in Python, but I still wanted to see if I did anything stupid here or missed any obvious optimization.

def kmp_table(word):
table = [0] * len(word)
position, candidate = 2, 0
table[0] = -1

while position < len(word):
if word[position - 1] == word[candidate]:
table[position] = candidate + 1
candidate += 1
position += 1
elif candidate > 0:
candidate = table[candidate]
else:
table[position] = 0
position += 1
return table

def kmp_search(text, word):
m, i = 0, 0
table = kmp_table(word)
while m + i < len(text):
if word[i] == text[m + i]:
if i == len(word) - 1:
return m
i += 1
else:
if table[i] > -1:
m += i - table[i]
i = table[i]
else:
m += 1
i = 0
return len(text)

• I'm not quite willing to put ~600:1 to CPython vs. native. Just wondering if explicitly moving len(text)/word changes anything. The specific case seems to be worst case for KMP and best case for BM(H). – greybeard Apr 19 '17 at 21:02
• I guess table = [0] * len(word) should be table = [0] * (len(word)+1). – pgs Apr 20 '17 at 18:22
• @pgs why? position is always less than len(word). – Graipher Apr 20 '17 at 18:29
• @greybeard That sounds like the start of a good answer ;-) – Graipher Apr 20 '17 at 18:30

One immediate, fairly significant improvement that I see would be to calculate len(text) and len(word) - 1 outside of the loop in kmp_search. This provided a 30%-50% reduction in time in my tests depending on the computer and Python version.

def kmp_search(text, word):
m, i = 0, 0
table = kmp_table(word)
LT = len(text)
LW = len(word) - 1
while m + i < LT:
if word[i] == text[m + i]:
if i == LW:
return m
i += 1
else:
if table[i] > -1:
m += i - table[i]
i = table[i]
else:
m += 1
i = 0
return LT

• but what about stackoverflow.com/questions/37848483/… which says it's O(1)? LW might be a speed-up, though. – Pimgd Apr 22 '17 at 10:44
• @Pimgd I believe it's the function call that's the issue, not the complexity of len – Jared Goguen Apr 22 '17 at 12:37
• Yeah, I guess caching the len does seem to reduce the runtime somewhat (even though it is not even close to the str.find time). I chose your answer, because it is a nice optimization to keep in mind, even though pimgd's answer gives a comparable speed-boost. – Graipher Apr 25 '17 at 13:23

    else:
if table[i] > -1:
m += i - table[i]
i = table[i]
else:
m += 1
i = 0


This sort of construct, an else which contains only an if-else chain, can be simply written as an elif-else chain.

    elif table[i] > -1:
m += i - table[i]
i = table[i]
else:
m += 1
i = 0


        table[position] = candidate + 1
candidate += 1


These statements seem weird, why not first add one and then set?

        candidate += 1
table[position] = candidate

• Your comments are valid and improve the readability and even speed things up slightly (who would've thought the simple fact that I'm calculating candidate + 1 twice would make a difference). Nevertheless I chose Jared's answer because it is more of an optimization and he needs the points more than you :) – Graipher Apr 25 '17 at 13:24