Tham khảo tài liệu 'thuật toán algorithms (phần 27)', 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 253 This leads to the very simple pattern-matching algorithm implemented below. The program assumes the same i ndex function as above but d 32 is used for efficiency the multiplications might be implemented as shifts . function rksearch integer const q 33554393 d 32 var hl h2 dM i integer begin dM l for i l to M-1 do dM d dM mod q hl 0 for i l to M do hl hl d index p i mod q for to M do mod q i l while hloh2 and i N-M do begin mod q mod q i i l end rksearch end The program first computes a hash for the pattern then a hash value h2 for the first M characters of the text. Also it computes the value of dM 1 modq in the variable dM. Then it proceeds through the text string using the technique above to compute the hash function for the M characters starting at position i for each i comparing each new hash value to hl. The prime q is chosen to be as large as possible but small enough that doesn t cause overflow this requires less mod operations then if we used the largest repesentable prime. An extra d q is added during the h2 calculation to make sure that everything stays positive so that the mod operation works as it should. This algorithm obviously takes time proportional to N M. Note that it really only finds a position in the text which has the same hash value as the pattern so to be sure we really should do a direct comparison of that text with the pattern. However the use of sucii a large value of q made possible by the mod computations and by the fact that we don t have to keep the actual hash table around make8 it extremely unlikely that a collision will occur. Theoretically this algorithm could still take NM steps in the unbelievably worst case but in practice the algorithm can be relied upon to take about N M steps. 254 CHAPTER 19 Multiple Searches The algorithms that we ve been discussing are all oriented towards a specific string searching problem find an occurrence of a given pattern in a given text string. If the same text string is to be
