Pattern matching decides whether there is an occurrences of a pattern P (impleme
ID: 3586068 • Letter: P
Question
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 naïve 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 aaa…ab. (6 pts)
Explanation / Answer
first of all, in the algorithm, the outer loop condition is incorrect.. It should be (n-m) instead of (m-n)
Now, Your questions:
*Prove that the algorithm patternmatch has a best run time of O(n), provided that the pattern is not in the text.
=> The algo first matches the first character of the pattern in the text and then proceeds subsequently only if the first charcter is matched.. (i.e. it works in the innner while loop).. So for the best case, where pattern doesn't appear in the text, the algorithm will never go inside inner while loop and only outer loop is executed (n-m) times, Hence complexity O(n-m)
* Prove that this algorithm has worst run time of O(n2)
=> think of the tring xxxxxxxxxx...xxxxy where we need to find a pattern xy. In this case we wil start with i=0 on outer loop and inner loop's first charcter also matches, so we will go inside the inner loop, but the pattern doesn't match completely.. Hence We move to next i value and so on.. We will find the pattern only at the very last i value..
So the outer loop is executed n times and the inner loop also gets executed n times (I am thinking both pattern and text to be of order n here) So the total complexity becomes O(n^2)