Kmp

KMP Algoritması

Giriş

Bilgisayar biliminde, KMP algoritması, bir “kelime” W’nin bir metin içerisindeki tüm oluşumlarını bulan bir dizge arama algoritmasıdır. Algoritma, ön işlem adı verilen bir adımda, kelimenin uzunluğuna göre bir öncel tablo oluşturur. Bu tablo, algoritmanın metin içerisinde ilerlemesini hızlandırmak için kullanılır.

KMP algoritması, 1971 yılında Donald Knuth, James H. Morris ve Vaughan Pratt tarafından geliştirilmiştir. Algoritma, basit ve etkili bir çözüm sunması nedeniyle, dizge arama algoritmalarının standart bir örneği olarak kabul edilir.

KMP Algoritmasının Çalışması

KMP algoritması, metin içerisinde ilerlemek için aşağıdaki adımları kullanır:

1. Metnin ilk karakterini kelimenin ilk karakteriyle karşılaştırır.
2. Karakterler eşleşiyorsa, algoritma bir sonraki karaktere ilerler.
3. **Karakterler eşleşmiyorsa, algoritma *öncel tabloya* bakar.**
4. Öncel tablo, algoritmanın kaçınması gereken karakterleri belirtir.
5. Algoritma, öncel tabloda belirtilen karakterleri atlar ve ardından 1. adıma döner.

Öncel Tablo

KMP algoritması, öncel tablo adı verilen bir tablo kullanır. Bu tablo, kelimenin uzunluğuna göre oluşturulur ve kelime içerisindeki tekrar eden alt dizeleri belirtir.

Örneğin, “ababc” kelimesinin öncel tablosu aşağıdaki gibidir:

i | 0 | 1 | 2 | 3
-- | -- | -- | -- | --
j | 0 | 1 | 2 | 0

Bu tabloda, i sütunu, kelimenin i. karakterini belirtir. j sütunu ise, i. karakterin eşleştiği kelimenin en son karakterinin j. karakterini belirtir.

Örneğin, i = 2 olduğunda, j = 0 değeri, “ba” alt dizininin “a” karakterinin “aba” kelimesinin 0. karakteriyle eşleştiğini gösterir.

KMP Algoritmasının Örneği

KMP algoritmasının çalışmasını aşağıdaki örnek ile inceleyelim.

Metin: abababc
Kelime: ab

1. Adım

Algoritma, metnin ilk karakteri olan a‘yı kelimenin ilk karakteri olan a ile karşılaştırır. Karakterler eşleştiği için, algoritma bir sonraki karaktere ilerler.

2. Adım

Algoritma, metnin ikinci karakteri olan b‘yi kelimenin ikinci karakteri olan b ile karşılaştırır. Karakterler eşleştiği için, algoritma bir sonraki karaktere ilerler.

3. Adım

Algoritma, metnin üçüncü karakteri olan b‘yi kelimenin üçüncü karakteri olan a ile karşılaştırır. Karakterler eşleşmediği için, algoritma öncel tabloya bakar.

4. Adım

Öncel tabloda, i = 3 olduğunda, j = 0 değeri, “ba” alt dizininin “a” karakterinin “aba” kelimesinin 0. karakteriyle eşleştiğini gösterir. Bu nedenle, algoritma “ba” alt dizisinin kalan karakterlerini atlar.

5. Adım

Algoritma, metnin dördüncü karakteri olan c‘yi kelimenin dördüncü karakteri olan c ile karşılaştırır. Karakterler eşleştiği için, algoritma bir sonraki karaktere ilerler.

6. Adım

Algoritma, metnin beşinci karakteri olan b‘yi kelimenin beşinci karakteri olan b ile karşılaştırır. Karakterler eşleştiği için, algoritma kelime bulunmuştur.

KMP Algoritmasının Karmaşıklığı

KMP algoritmasının karmaşıklığı, O(m+n)‘dir. Burada, m kelimenin uzunluğunu ve n metnin uzunluğunu belirtir.

KMP Algoritmasının Avantajları

KMP algoritmasının avantajları şunlardır:

*