tailieunhanh - Thuật toán Algorithms (Phần 26)

Tham khảo tài liệu 'thuật toán algorithms (phần 26)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | STRING SEARCHING 243 and has limited the extent to which they are used. In fact the story goes that an unknown systems programmer found Morris algorithm too difficult to understand and replaced it with a brute-force implementation. In 1980 R. M. Karp and M. 0. Rabin observed that the problem is not as different from the standard searching problem as it had seemed and came up with an algorithm almost as simple as the brute-force algorithm which virtually always runs in time proportional to M N. Furthermore their algorithm extends easily to two-dimensional patterns and text which makes it more useful than the others for picture processing. This story illustrates that the search for a better algorithm is still very often justified one suspects that there are still more developments on the horizon even for this problem. Brute-Force Algorithm The obvious method for pattern matching that immediately comes to mind is just to check for each possible position in the text at which the pattern could match whether it does in fact match. The following program searches in this way for the first occurrence of a pattern p 1. .M in a text string a 1. .N function brutesearch integer var i j integer begin i l j l repeat if a i p j then begin end else begin i i j 2 j l end until or if j M then else end The program keeps one pointer i into the text and another pointer j into the pattern. As long as they point to matching characters both pointers are incremented. If the end of the pattern is reached then a match has been found. If i and j point to mismatching characters then j is reset to point to the beginning of the pattern and i is reset to correspond to moving the pattern to the right one position for matching against the text. If the end of the text is reached then there is no match. If the pattern does not occur in the text the value is returned. In a text-editing application the inner loop of this program is seldom iterated and the running time is very nearly proportional to the