B I Consider The Bruteforce String Matching Algorithm Given In Appendix B Provide An Input Text String T Of 8 Chara 1 (40.92 KiB) Viewed 30 times
(b) (i) Consider the BruteForce String Matching Algorithm given in Appendix B. Provide an input text string T of 8 characters and a Pattern P of 3 characters which would produce the worst-case behavior of the algorithm. (ii) For the text and pattern which you have chosen, determine the number of comparison performed by the BruteForce String Matching Algorithm. (iii) Let C(n) be the number of comparisons required to execute the BruteForce String Matching Algorithm on a text string of n characters and a pattern P of m characters. Write an equation for the number of comparisons made by the algorithm in the worst case. Justify each term in your equation.
Appendix B: Brute Force String Matching ALGORITHM Brute ForceString Match(T[0..n-1], P[0..m - 1]) //Implements brute-force string matching //Input: An array T[0..n - 1] of n characters representing a text and 11 an array P[0..m - 1] of m characters representing a pattern //Output: The index of the first character in the text that starts a matching substring or -1 if the search is unsuccessful 11 for i 0 to n - m do ← j-0 while j<m and P[j] = T[i+j] do j+j+1 if j = m return i return -1
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!