TechCodeview

Knuth-Morris ve Pratt, dize eşleştirme sorunu için doğrusal bir zaman algoritması geliştirdi. O(n)'nin eşleştirme süresi, eşleştirilecek 'p' modelinin bazı elemanları ile karşılaştırmada daha önce yer alan bir 'S' elemanı ile karşılaştırmanın önlenmesiyle elde edilir. yani 'S' dizisinde geri izleme asla gerçekleşmez

KMP Algoritmasının Bileşenleri:

1. Önek Fonksiyonu (Π): Bir model için Önek Fonksiyonu, Π, modelin kendi kaymasına karşı nasıl eşleştiğine ilişkin bilgiyi kapsar. Bu bilgi 'p' kalıbının yararsız bir şekilde değişmesini önlemek için kullanılabilir. Başka bir deyişle, bu, 'S' dizisinin geriye doğru izlenmesinin önlenmesini sağlar.

2. KMP Maçları: Giriş olarak 'S' dizgisi, 'p' modeli ve 'Π' önek fonksiyonu ile, 'S'de 'p' oluşumunu bulun ve oluşumların bulunduğu 'p' kaydırma sayısını döndürür.

Önek Fonksiyonu (Π)

Aşağıdaki sözde kod önek fonksiyonunu (Π) hesaplar:

 <strong>COMPUTE- PREFIX- FUNCTION (P)</strong> 1. m &#x2190;length [P] //&apos;p&apos; pattern to be matched 2. &#x3A0; [1] &#x2190; 0 3. k &#x2190; 0 4. for q &#x2190; 2 to m 5. do while k &gt; 0 and P [k + 1] &#x2260; P [q] 6. do k &#x2190; &#x3A0; [k] 7. If P [k + 1] = P [q] 8. then k&#x2190; k + 1 9. &#x3A0; [q] &#x2190; k 10. Return &#x3A0; 

Çalışma Süresi Analizi:

Önek fonksiyonunun hesaplanmasına yönelik yukarıdaki sözde kodda, 4. adımdan 10. adıma kadar olan for döngüsü 'm' kez çalışır. Adım 1'den Adım 3'e kadar sabit zaman alır. Dolayısıyla önek fonksiyonunu hesaplamanın çalışma süresi O(m)'dir.

Örnek: Aşağıdaki 'p' modeli için Π'yi hesaplayın:

int'i string'e çevirme java

Çözüm:

 Initially: m = length [p] = 7 Π [1] = 0 k = 0 

6 kez yinelemeden sonra önek işlevi hesaplaması tamamlanır:

KMP eşleşir:

Giriş olarak 'p' modeli, 'S' dizisi ve 'Π' önek fonksiyonuna sahip KMP Eşleştirici, S'de bir p eşleşmesi bulur. Aşağıdaki sözde kod, KMP algoritmasının eşleşen bileşenini hesaplar:

 <strong>KMP-MATCHER (T, P)</strong> 1. n &#x2190; length [T] 2. m &#x2190; length [P] 3. &#x3A0;&#x2190; COMPUTE-PREFIX-FUNCTION (P) 4. q &#x2190; 0 // numbers of characters matched 5. for i &#x2190; 1 to n // scan S from left to right 6. do while q &gt; 0 and P [q + 1] &#x2260; T [i] 7. do q &#x2190; &#x3A0; [q] // next character does not match 8. If P [q + 1] = T [i] 9. then q &#x2190; q + 1 // next character matches 10. If q = m // is all of p matched? 11. then print &apos;Pattern occurs with shift&apos; i - m 12. q &#x2190; &#x3A0; [q] // look for the next match 

Çalışma Süresi Analizi:

5. adımda başlayan for döngüsü 'n' kez, yani 'S' dizisinin uzunluğu kadar çalışır. Adım 1'den adım 4'e kadar sabit süreler aldığından, döngünün çalışma süresine bu hakimdir. Dolayısıyla eşleştirme fonksiyonunun çalışma süresi O(n)'dir.

Örnek: Aşağıdaki gibi bir 'T' dizisi ve 'P' modeli verildiğinde:

'P'nin 'T'de bulunup bulunmadığını bulmak için KMP Algoritmasını çalıştıralım.

'p' önek işlevi için, ? daha önce hesaplanmıştı ve şu şekildeydi:

Çözüm:

 Initially: n = size of T = 15 m = size of P = 7 

'P' kalıbının 'T' dizisinde karmaşıklık meydana getirdiği bulundu. Maçın bulunması için gerçekleşen toplam vardiya sayısı i-m = 13 - 7 = 6 vardiyadır.