The pattern-matching problem is as follows: Given a string, S, of text, and a pat- tern, P, ?nd the ?rst occurrence of P in S. Approximate pattern matching allows k mismatches of three types:
(1) A character can be in S that is not in P.
(2) A character can be in P that is not in S.
(3) P and S can differ in a position.
As an example, if we are searching for the pattern "textbook" with at most three mismatches in the string "data structures txtborpk", we ?nd a match (insert an e, change an r to an o, delete a p). Give an O(MN) algorithm to solve the approximate string matching problem, where M = |P| and N = |S|.