Pattern matching decides whether there is an occurrences of a pattern P (implemented as an array of characters over a given alphabet) in a text (or string) T, also implemented as an array of characters over the same alphabet. The nave pattern-matching algorithm consecutively compares the pattern with a given location in the text, checking all characters from the left to the right. In pseudo-code, the algorithm runs like this:

function patternmatch ( character text[1 ... n]

, character pattern[1 ... m])

{

for ( integer i = 0; i < m n; i++ ) {

integer j = 1;

while (j < m and pattern[j+1] == text[i+j+1] )

{

j = j+1;

}

if( j == m) return true;

}

return false; //at end of text, no occurrence found

}

Assume that the length m of the pattern is much smaller than the length n of the text.

Prove that the algorithm patternmatch has a best run time of O(n), provided that the pattern is not in the text. (Otherwise, finding the pattern a in the text abcdefg takes O(1) operations.) (4 pts)

Prove that this algorithm has worst run time of O(n2). Hint: You can use strings of type aaaab. (6 pts)