Discuss at length both the best and worst case of the pattern-matching algorithm.

Question

What will be an ideal response?

Answer 1

Both the best case and the worst case of this algorithm can occur when the pattern is not in the text at all. The difference hinges on exactly how the pattern fails to be in the text. The best case occurs if the first character of the pattern is nowhere in the text, as in

Text: KLMNPQRSTX
Pattern: ABC

In this case, n- m + 1 comparisons are required, trying (unsuccessfully) to match P1 with T1, T2, … , Tn-m+1 in turn. Each comparison fails, and the algorithm slides the pattern forward to try again at the next position in the text. The maximum amount of work is done if the pattern almost occurs
everywhere in the text. Consider, for example, the following case:

Text: AAAAAAAAA
Pattern: AAAB

Starting with T1, the first text character, the match with the first pattern character is successful. The match with the second text character and the second pattern character is also successful. Indeed m- 1 characters of the pattern match with the text before the mth comparison proves a failure. The process starts over from the second text character, T2. Once again, m comparisons are required to find a mismatch. Altogether, m comparisons are required for each of the n- m + 1 starting positions in the text. Another version of the worst case occurs when the pattern is found at each location in the text, as in

Text: AAAAAAAAA
Pattern: AAAA

This results in the same comparisons that are done for the other worst case. The only difference is that the comparison of the last pattern character is successful.