მოძრავი ჰეში და რაბინ-კარპი

ჰეშ-ფუნქციები ჰეშ-ცხრილის გაკვეთილში უკვე გაიცანი: გასაღები რიცხვად ვაქციოთ და შემდეგ ეს რიცხვი გამოვიყენოთ. სტრიქონებისთვის სტანდარტული არჩევანია პოლინომიალური ჰეში. სტრიქონი წავიკითხოთ, როგორც p-ფუძიანი რიცხვის ციფრები:

h(s) = s[0]·p^(m−1) + s[1]·p^(m−2) + … + s[m−1] (mod M)

როცა A=1, B=2, p = 31 და M = 97, სტრიქონი ABAB ხდება 27. ტოლ სტრიქონებს ყოველთვის ტოლი ჰეში აქვთ. განსხვავებულებს ჩვეულებრივ განსხვავებული.

მას მარცხნიდან მარჯვნივ ვითვლით: h = h·p + code(c), ყოველ ნაბიჯზე ვიღებთ mod M-ს, რომ რიცხვები პატარა დარჩეს.

ჰეში უამრავ შესაძლო სტრიქონს M მნიშვნელობაში ატევს, ამიტომ ორ განსხვავებულ სტრიქონს ზოგჯერ ერთი ჰეში ექნება. ესაა შეჯახება (კოლიზია). M = 97-ისას AA-საც და DE-საც ჰეში 32 აქვს.

ამიტომ, როცა ფანჯრის ჰეში შაბლონისას დაემთხვევა, რაბინ-კარპი დამთხვევის გამოცხადებამდე ნამდვილ სიმბოლოებს ადარებს. ცრუ განგაში O(m) ღირს, მაგრამ არასწორ პასუხს არასოდეს იძლევა.

რეალურ კოდში გამოიყენე დიდი მარტივი რიცხვი, მაგ. M = 10⁹ + 7, შემთხვევითი ფუძით p, ან ერთდროულად ორი მოდული. მაშინ შეჯახებები იმდენად იშვიათია, რომ მოსალოდნელი დრო O(n + m)-ია. იგივე მოძრავი იდეა პასუხობს კითხვას „ტოლია თუ არა ეს ორი ქვესტრიქონი?“ O(1)-ში, პრეფიქსული ჰეშების O(n) წინასწარი დათვლის შემდეგ.