Rabin–Karp ve Aho–Corasick

Rabin–Karp rolling hash ile sabit uzunluktaki pencereleri karşılaştırır. Eski karakterin katkısını çıkar, tabanla kaydır, yeni karakteri ekle ve modulo uygula. Hash eşitliği gerçek eşleşme kanıtı değildir. Doğrudan substring kontrolü deterministic doğruluğu sağlar fakat kötü collision durumunda maliyet artar; double hashing olasılığı düşürür, sıfırlamaz.

Aho–Corasick birçok pattern'ı trie'a koyar, failure links ile bir mismatch sonrası en uzun uygun suffix durumuna geçer. Output links terminal pattern'ları raporlar; sadece mevcut düğümün terminalini kontrol etmek suffix pattern'ları kaçırır. BFS, failure links'i önce daha kısa durumlar hazır olacak sırada kurar.

Rabin–Karp aynı uzunluktaki birçok pattern için hash bucket'larıyla kullanılabilir; değişken uzunluk başka maliyetler yaratır. Aho–Corasick toplam pattern uzunluğu ve gerçek çıktı sayısıyla analiz edilir. Bir küfür filtresinde normalization ve boundary politikası false positive'ları belirler; algoritma etik/dilsel kararları kendiliğinden çözmez.

def rolling_hashes(text, width, base=257, mod=1000000007):
    if not 1 <= width <= len(text): return []
    high=pow(base,width-1,mod); h=0
    for c in text[:width]: h=(h*base+ord(c))%mod
    result=[h]
    for i in range(width,len(text)):
        h=((h-ord(text[i-width])*high)*base+ord(text[i]))%mod
        result.append(h)
    return result
assert len(rolling_hashes("ababa",3)) == 3