Satr algoritmlari

Matnda andoza qidirish va qism satrlarni tez solishtirish. Oddiy qidiruv O(n · m) vaqt oladi, quyidagi usullar esa O(n + m).

Prefiks-funksiya (KMP)

pi[i] — s[:i + 1] ning eng uzun xos prefiksi uzunligi, bu prefiks ayni paytda suffiks ham bo‘lishi kerak.

def prefix_function(s):
    pi = [0] * len(s)
    for i in range(1, len(s)):
        k = pi[i - 1]
        while k and s[i] != s[k]:
            k = pi[k - 1]
        if s[i] == s[k]:
            k += 1
        pi[i] = k
    return pi

p andozani t ichidan izlash: p + "#" + t uchun hisoblang. pi qiymati len(p) ga teng bo‘lgan joyda andoza tugaydi.

Z-funksiya

z[i] — s va s[i:] ning eng uzun umumiy prefiksi.

def z_function(s):
    n = len(s)
    z = [0] * n
    l = r = 0
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > r:
            l, r = i, i + z[i]
    return z

Polinomial hash

Har prefiks uchun hash hisoblansa, istalgan ikki qism satrni O(1) da solishtirish mumkin.

MOD, B = (1 << 61) - 1, 131
h, pw = [0] * (n + 1), [1] * (n + 1)
for i, ch in enumerate(s):
    h[i + 1] = (h[i] * B + ord(ch)) % MOD
    pw[i + 1] = pw[i] * B % MOD

def get(l, r):                     # s[l:r] ning hashi
    return (h[r] - h[l] * pw[r - l]) % MOD

Hashlar teng bo‘lsa, satrlar deyarli albatta teng. To‘qnashuv ehtimoli juda kichik, lekin nol emas.