Pattern Matching & Back-of-the-Envelope Estimations The pattern matching problem can be stated as: Score Given a (usuall

[answerhappygod]

Pattern Matching & Back-of-the-Envelope Estimations
The pattern matching problem can be stated as: Score
Given a (usually long) text string t and a (usually shorter)pattern p find where or if the pattern p occurs in t. Assume thelength of t is n and the length of p is m Several algorithms werepresented in the course notes to solve the pattern matching problemHere are two: • Brute-Force: The notes state the time complexity ofthis approach to solving the problem is O(mn). •Knuth-Morris-Pratt: The notes state the time complexity of thisapproach to solving the problem is O(m + n). The human genome isapproximately three billion base pairs in size. the average lengthof a gene is approximately 30 thousand base pairs. Let m = 30, 000and n = 3, 000, 000, 000 There are about 30, 000, 000 seconds in ayear. Assume a character-to-character comparison takes 1microsecond. Estimate the time it will take to run a brute-forcealgorithm. Do the same for the KMP algorithm.