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!