What is the worst case for KMP string search algorithm? [closed]

Question

Can anyone suggest me a worst case "text string - pattern pair" for testing a KMP algorithm implementation?

Answer 1

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)

Answer 2

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