Özet - String matching

KMP ile eşleşme indeksini yazdıran mini görev yaparsın.

Özet - String matching

Bu grupta beş string eşleme yöntemi gördük: KMP, Rabin-Karp, Boyer-Moore, Z-algoritması ve suffix array.

KMP önek tablosuyla, Rabin-Karp yuvarlanan hash ile, Boyer-Moore kötü karakter yöntemiyle doğrusal zaman sunar. Z-algoritması ve suffix array ise daha geniş görevlerde kullanılır.

Şimdi KMP'yi küçük bir görevle tekrar edeceğiz.

Uygulama kmp_search mini görev

kmp_search(text, pattern) yaz. İlk eşleşme indeksini döndür; yoksa -1. print(kmp_search("mississippi", "issi")) ile 1 yazdır.

Örnek çözümü göster

def kmp_search(text, pattern):
    # KMP ile ilk eşleşme
    n, m = len(text), len(pattern)
    lps = [0] * m
    length = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    i = j = 0
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == m:
                return i - j
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return -1
print(kmp_search("mississippi", "issi"))

Kendini test et

Hash çakışması riski en az olan yöntem?
- Rabin-Karp
- Boyer-Moore kötü karakter
- KMP
- Yuvarlanan hash
Cevabı göster

KMP — KMP hash kullanmaz, çakışma riski yoktur.

KMP lps değeri

# pattern = "abcabd"
# lps[4] = ____

Cevabı göster

# pattern = "abcabd"
# lps[4] = 2

Yöntem-özellik

KMP

Önek tablosu
Rabin-Karp

Yuvarlanan hash
Boyer-Moore

Kötü karakter
Z-algoritması

Z-dizisi

Sıradaki ders: Vektör çapraz çarpım

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler