Brute-Force String Matching Recall the string-matching problem introduced in Section 1.3: given a string of n characters called the text and a string of m characters (mn) called the pattern, find a substring of the text that matches the pattern. To put it more pr want to find i-the index of the leftmost character of the first matching substring in the text-such that t.-Po,.A+/ pj, . . . ,--1-Pm-1. ecisely, we 4 ext T PoP P-1 pattern P If matches other than the first one need to be found, a string-matching algorithm can simply continue working until the entire text is exhausted. A brute-force algorithm for the string-matching problem is quite obvious: align the pattern against the first m characters of the text and start matching the corresponding pairs of characters from left to right until either all m p of the characters match (then encoun and character comparisons are the pattern and its counterpart in the text. Note that the last the algorithm can stop) or a mismatching pair is tered. In the latter case, the pattern is shifted one position to the right resumed, starting again with the first character of position in the text that can still be a beginning of a matching substring is n -m(provided the text's positions are indexed from 0ton 1). Beyond that position, there are not enough characters to match the entire pattern; hence, the comparisons there. algorithm need not make any ALGORITHM BruteForceStringMatch(.n-1], Plo.m-1]) The algorithm implements brute-force string matchintg. Input: An array T[O.n-1]of n characters representing a text; /l an array P[0..m -1 of m characters representing a pattern. Output: The position of the first character in the text that starts the first matching substring if the search is successful and-1 otherwise. for i 0ton-in do while j m and P[J]= T[i + j] do jj+1 if jm return i return -1 An operation of the algorithm is illustrated in Figure 3.3