Can anyone suggest me a worst case "text string - pattern pair" for testing a KMP algorithm implementation?
I would say a pattern like
xx........x
| n times |
and a string like
xxx.........xyx...........xy....
| n-1 times | | n-1 times |
would be one of the worst cases, but it's still O(m+n)
You can find anything on KMP algorithm here :
KMP ALGORITHM
Quick extract :
Knuth, Morris and Pratt discovered first linear time string-matching algorithm by following a tight analysis of the naïve algorithm. Knuth-Morris-Pratt algorithm keeps the information that naïve approach wasted gathered during the scan of the text. By avoiding this waste of information, it achieves a running time of O(n + m), which is optimal in the worst case sense. That is, in the worst case Knuth-Morris-Pratt algorithm we have to examine all the characters in the text and pattern at least once.
You should be able to calrify what you understand of the algorithm and find what you need there.
hope it helps
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With