The data is the string S[1..n] and the pattern P[0.. m - 1], where 1...

  

Transcribed Image Text:

The data is the string S[1..n] and the pattern P[0.. m - 1], where 1 <m <n. The algorithm below determines the position of in the P pattern in the S string, i.e. = p if Sp.. p+m - 1] = P, a l=n-m + 1 if the pattern P is not a substring of S. MATCH(P, S, m, n) 1 l 0 2 matched false 3 while <n-m A-matched 4 do ll + 1 5 6 7 8 9 10 return l T 0 matched true while r <m ^ matched do matched (P[r]=S[l+r]) r+r+1 ← How many comparisons of string and pattern symbols (instructions on line 8) do the above algorithm in the pessimistic case? The data is the string S[1..n] and the pattern P[0.. m - 1], where 1 <m <n. The algorithm below determines the position of in the P pattern in the S string, i.e. = p if Sp.. p+m - 1] = P, a l=n-m + 1 if the pattern P is not a substring of S. MATCH(P, S, m, n) 1 l 0 2 matched false 3 while <n-m A-matched 4 do ll + 1 5 6 7 8 9 10 return l T 0 matched true while r <m ^ matched do matched (P[r]=S[l+r]) r+r+1 ← How many comparisons of string and pattern symbols (instructions on line 8) do the above algorithm in the pessimistic case?

Answer rating: 100% (QA)

The algorithm provided is a simple pattern matching algorithm which ... View the full answer