Đang chuẩn bị liên kết để tải về tài liệu:
Thuật toán Algorithms (Phần 27)

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