Boyer-Moore

Boyer-Moore kötü karakter kuralıyla eşleme öğrenirsin.

Boyer-Moore

Boyer-Moore, örüntüyü sağdan sola tarayarak eşleşme arar. Bu yön, büyük kaydırmalar yapmayı sağlar; çoğu durumda metnin yalnızca küçük bir bölümünü gözden geçirir.

İki ilke kullanır: kötü karakter ve iyi sonek. Burada kötü karakter yöntemini işleyeceğiz.

Kötü karakter yöntemi, uyuşmazlık bulunan metin karakterine göre örüntüyü kaydırır; böylece uyuşmayan karakter örüntüye hizalanır.

Kötü karakter tablosu

Kötü karakter tablosu, her karakter için örüntüdeki son görülme indeksini saklar. Uyuşmazlıkta, kaydırma miktarı max(1, j - bad[text[i]]) olarak hesaplanır.

Eğer uyuşmayan karakter örüntüde yoksa, örüntüyü tamamen bu karakterin sağına kaydırırız. Tablo bir hazırlık adımıdır ve O(m + |alfabe|) zamanda kurulur.

Bu ilke tek başına bile çoğu pratik durumda hızlı çalışır.

Uygulama boyer_moore fonksiyonu

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

Örnek çözümü göster

def boyer_moore(text, pattern):
    # Kötü karakter yöntemi ile ara
    n, m = len(text), len(pattern)
    if m == 0:
        return 0
    bad = {}
    for i in range(m):
        bad[pattern[i]] = i
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[i + j]:
            j -= 1
        if j < 0:
            return i
        shift = j - bad.get(text[i + j], -1)
        if shift < 1:
            shift = 1
        i += shift
    return -1
print(boyer_moore("konfeksiyonmakine", "makine"))

Kendini test et

Boyer-Moore kavramları

sağdan sola

Tarama yönü
kötü karakter

Kaydırma ilkesi
iyi sonek

İkinci ilke
büyük kaydırma

Hız avantajı
Kötü karakter yöntemi ne yapar?
```
shift = j - bad.get(text[i+j], -1)
```
- Tabloyu yeniden kurar
- Örüntüyü bir adım kaydırır
- Eşleşmeyi iptal eder
- Uyuşmazlık karakterine göre kaydırır
Cevabı göster

Uyuşmazlık karakterine göre kaydırır — Kötü karakter yöntemi uyuşmazlık karakterine göre kaydırır.

kötü karakter kaydırması

shift = j - bad.get(text[i + j], ____)

Cevabı göster

shift = j - bad.get(text[i + j], -1)

Sıradaki ders: Z-algoritması

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler