Alt sətir axtarışı: sadə və Rabin-Karp

Alt sətir axtarışı text içində pat nümunəsinin bütün yerlərini tapmaq məsələsidir (n = len(text), m = len(pat)). Sadə üsul O(nm) vaxt aparır. Rabin-Karp alqoritmi hər pəncərəni simvol-simvol yox, yuvarlanan hesh ilə müqayisə edir və orta halda O(n + m) işləyir. Sətirlərlə iş: palindrom və anaqramlar.

Sadə axtarış

Nümunəni mətnin hər i mövqeyinə (0..n-m) qoyub soldan sağa müqayisə edirik; uyğunsuzluqda bir mövqe sürüşürük. Mövqelərin sayı n - m + 1, hər birində ən çox m müqayisə, deməli ən pis halda O(nm). Adi mətndə uyğunsuzluq adətən ilk simvollarda tapılır və vaxt O(n)-ə yaxın olur, lakin aaaa...ab kimi təkrarlı verilənlərdə (DNT, ikili mətnlər) ən pis hal real olur. Yaddaş O(1).

def naive(text, pat):
    n, m = len(text), len(pat)
    result, comps = [], 0
    for i in range(n - m + 1):
        j = 0
        while j < m:
            comps += 1
            if text[i + j] != pat[j]:
                break
            j += 1
        if j == m:
            result.append(i)
    return result, comps

print(naive("abracadabra", "abra"))
print(naive("a" * 20, "a" * 9 + "b"))

([0, 7], 16)
([], 110)

Yuvarlanan hesh

Sətri əsası B olan ədəd kimi oxuyuruq: h(s) = s[0]·B^(m-1) + s[1]·B^(m-2) + ... + s[m-1], nəticəni böyük sadə M-ə görə qalıqla saxlayırıq. Pəncərə bir simvol sağa sürüşəndə yeni heş köhnədən O(1)-də alınır: h_new = (h_old - s[i]·B^(m-1))·B + s[i+m] (mod M). Burada B^(m-1) mod M əvvəlcədən bir dəfə hesablanır (pow(B, m - 1, M)).