KMP algoritması
- Algoritmalar kursu
- Uzman seviye
- Ders 13/41
- 4 dk
KMP ile önek tablolu string eşleme öğrenirsin.
KMP algoritması
KMP algoritması, bir metin içinde örüntüyü doğrusal zamanda arar. Karmaşıklığı O(n+m)'dir; bu, naif yöntemin O(n·m)'sine göre belirgin iyileşmedir.
Sorunun temel fikri önek tablosu (lps) hazırlamaktır. lps[i], örüntünün ilk i+1 karakteri için hem önek hem sonek olan en uzun proper önekin uzunluğudur.
Bu sayede bir uyuşmazlıkta örüntüyü başa değil lps değerine göre kaydırırız; tekrar karşılaştırma yapmayız.
lps tablosu kurulumu
lps tablosunu kurarken iki gösterge kullanırız: i örüntüyü tarar, length şu anki eşleşen önek uzunluğunu tutar.
pattern[i] == pattern[length] ise her ikisini artırır ve lps[i] = length yazarız. Uyuşmazlıkta length'i lps[length-1]'e geri çekeriz; bu, önek tablosunun özyinelemeli doğasını yansıtır.
Bu adım O(m)'dir; örüntüyü bir kez tarar.
Uygulama kmp_search fonksiyonu
kmp_search(text, pattern) yaz. Örüntünün metin içindeki ilk eşleşme indeksini döndür; yoksa -1. print(kmp_search("abcabcabcd", "abcabcd")) ile 3 yazdır.
Başlangıç kodu
def kmp_search(text, pattern):
# İlk eşleşme indeksini döndürÖrnek çözüm
def kmp_search(text, pattern):
# İlk eşleşme indeksini döndür
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("abcabcabcd", "abcabcd"))Beklenen çıktı
3
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 lps[i] neyi saklar?
lps = [0, 0, 0, 1, 2, 3, 0]- Örüntünün toplam uzunluğunu
- Aynı zamanda önek ve sonek olan en uzun proper önekin uzunluğunu Doğru cevap
- Metnin i. karakterinin ASCII değerini
- Eşleşmenin başlangıç indeksini
Açıklama: lps[i], aynı anda önek ve sonek olan en uzun proper önekin uzunluğudur.
2 lps geri çekme
if pattern[i] == pattern[length]:
length += 1
lps[i] = ____
i += 1if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1Açıklama: lps[i] = length yazılır.
3 KMP kavramları
| Kavram | Anlamı |
|---|---|
lps |
Önek tablosu |
O(n+m) |
Doğrusal zaman |
proper önek |
Tüm dize hariç |
kaydırma |
lps ile geri çekme |