Meydan okuma 2
- Algoritmalar kursu
- Uzman seviye
- Ders 38/41
- 4 dk
KMP ile eşleşme indeksini yazdırırsın.
Meydan okuma 2 - KMP
İkinci meydan okuma, KMP string eşleme algoritmasını yoklar. Önek tablosu (lps) ile bir örüntüyü metinde doğrusal zamanda arar.
Yukarıdaki count_doublings fonksiyonu hazırdır; sen kmp_search yazacaksın. Önce lps tablosunu kur, sonra iki göstergeyle tara.
Bu meydan okuma, birikimli zincirin ikinci halkasıdır.
Uygulama kmp_search fonksiyonu
kmp_search(text, pattern) yaz. İlk eşleşme indeksini döndür; yoksa -1. print(kmp_search("abcabcabcd", "abcabcd")) ile 3 yazdır. count_doublings fonksiyonu yukarıda hazırdır.
Başlangıç kodu
def count_doublings(n):
count = 0
size = 1
last = 0
for i in range(n):
if last == size:
size *= 2
count += 1
last += 1
return count
def kmp_search(text, pattern):
# İlk eşleşme indeksini döndürÖrnek çözüm
def kmp_search(text, pattern):
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
elif 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
elif 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 tablosu
Soru
lps = [0] * ____
length = 0
Cevap
lps = [0] * m
length = 0Açıklama: lps, örüntü uzunluğu m kadar olur.
2 KMP kavramları
| Kavram | Anlamı |
|---|---|
lps |
Önek tablosu |
O(n+m) |
Doğrusal zaman |
i - j |
Eşleşme indeksi |
-1 |
Eşleşme yok |
3 KMP'nin karmaşıklığı nedir?
- O(n·m)
- O(n+m) Doğru cevap
- O(n²)
- O(2ⁿ)
Açıklama: KMP O(n+m) zaman alır.