Özet - String matching
- Algoritmalar kursu
- Uzman seviye
- Ders 18/41
- 4 dk
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.
Başlangıç kodu
def kmp_search(text, pattern):
# KMP ile ilk eşleşmeÖrnek çözüm
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"))Beklenen çıktı
1
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Hash çakışması riski en az olan yöntem?
- Rabin-Karp
- Boyer-Moore kötü karakter
- KMP Doğru cevap
- Yuvarlanan hash
Açıklama: KMP hash kullanmaz, çakışma riski yoktur.
2 KMP lps değeri
Soru
# pattern = "abcabd"
# lps[4] = ____
Cevap
# pattern = "abcabd"
# lps[4] = 2Açıklama: lps[4] = 2 ("ab" önek ve sonek).
3 Yöntem-özellik
| Kavram | Anlamı |
|---|---|
KMP |
Önek tablosu |
Rabin-Karp |
Yuvarlanan hash |
Boyer-Moore |
Kötü karakter |
Z-algoritması |
Z-dizisi |