Knuth-Morris-Pratt alt algoritminin alt sətir axtarış prinsipi haqqında izah edin.
sobes.tech Süni İntellekt
AI-dan cavab
Knuth-Morris-Pratt (KMP) algoritması, karakterleri tekrar tekrar karşılaştırmadan, bir alt diziyi bir dizide doğrusal zamanda aramak için tasarlanmıştır.
Ana fikir, alt dizinin önceden bir ön ek fonksiyonları dizisi (veya "π-dizi") hesaplamaktır; bu dizi, başarısız bir karşılaştırma sırasında kaç karakterin alt dizinin başlangıcıyla eşleştiğini gösterir. Bu, uyuşmazlık durumunda, orijinal dizide geriye dönmek yerine, alt diziyi en uygun sayıda kaydırmaya olanak tanır.
Örnek:
- Metin: "ABABDABACDABABCABAB"
- Aranan alt dizi: "ABABCABAB"
Algoritma önce alt dizinin ön ek fonksiyonunu oluşturur, sonra metin üzerinde karakterleri karşılaştırarak ilerler. Uyuşmazlık durumunda, ön ek fonksiyonunu kullanarak, karşılaştırmaya hangi karakterden devam edeceğini belirler, başa dönmeden.
Bu, O(n + m) karmaşıklığı sağlar; burada n metnin uzunluğu, m ise alt dizinin uzunluğudur ve bu, basit aramadan daha etkilidir.