I’m curious in the worst-case running time of the Knuth Morris Pratt Algorithm for String Matching:

Assume that T = AAAAB and P = AB.

The prefix table in this situation is:

**#P Sk-D**

**0 A 0**

**1 B 0**

As I go over T, I compare P values to it: AB AAAAB At Cell#0, there is a partial match. We transfer P to the next cell since the skip distance for Cell#0 for P is zero: AB AAAAB

As a result, the identical situation will be repeated three times (6 times) until T matches the substring “AB” in P. (2 more comparisons). There were a total of eight comparisons: Length of P * Length of T - Length of T = 5 * 2 - 2 = 8 = O(mn) - O(m) = O (mn). This is obviously not O(m+n), the worst-case constraint for the KMP method.

What am I doing incorrectly? For your convenience, I read this post by scaler topics, but I believe my prefix table is inaccurate. However, if I follow the definition of “longest suffix in P that is also a prefix in P,” I cannot see any additional values in the prefix table.

I would appreciate any assistance.

Thank you very much!