Knuth-Morris-Pratt algoritması

Bu algoritma failure function yazısında oluşturduğumuz tabloyu kullanarak aradığımız metni uyumsuzluğun olduğu konuma göre değişik miktarlarda kaydırmaktadır. Bu şekilde aranan metni her adımda bir karakter kaydırma algoritmasına göre bir iyileştirme elde edeceğiz.

Aşağıdaki linkle animasyon sayfasına ulaşabilirsiniz. Sayfa yüklendiği zaman aranan metin için daha önceki yazıda tanımlanan tabloyu hesaplayacak. Ardından ana metni ve aranan metni gösterip uyumlu karakterleri yeşil renkle, uyumsuz olan ilk karakteri de kırmızı ile gösterecek. Ondan sonra uyumlu ortak metin uzunluğundan tabloda seçilen sütunu yeşi ile gösterip oradan kaydırma miktarını okuyacak. Aranan metin bu miktar kadar kaydırıldıktan sonra aynı işlemleri tekrarlıyor. Animasyon aranan metin bulunana kadar devam ediyor.

Animasyon

Bir yanıt yazın