Knuth–Morris–Pratt Algoritması

Giriş
Knuth–Morris–Pratt (KMP) Algoritması string aramayı (string matching) hızlandıran bir algoritma. Özelliği bir tablo kullanması. Tablonun doldurulma şekli Wikipedia'da ve geeksforgeeks sitesinde farklı şekillerde gösteriliyor.

Örnek
Aradığımız string "ABCD" olsun. T tablosu şöyledir.
A  B  C  D
-1  0   0  0

Tabloda 0 olması bu indekse kadar olan sayıdaki karakter atlanabilir anlamına gelir. Bu karaktere kadar prefix yoktur.
Tabloda artı sayı olması az karakter atlanacağı anlamına gelir. Bu karaktere kadar prefix vardır.

Kodlarken T tablosundaki hangi indekste eşleşme hatası olursa i - T [i] kadar hedef string'de atlarız.

1. A harfinde eşleşme olmasın
0 - T[0] yani 0 - (-1) = 1 harf atlanır.

Hedef    : BAAAA
Örüntü : ABCD
Şöyle olur
Hedef   : BAAAA
Örüntü :   ABCD

2. B harfinde eşleşme olmasın.
1 - T[1] yani 1 -0 = 1 harf atlanır.

Hedef   : AAAAA
Örüntü : ABCD
Şöyle olur
Hedef   : AAAAA
Örüntü :   ABCD

3. C harfinde eşleşme olmasın.
2 - T[2] yani 2 -0 = 2 harf atlanır.

Hedef  : ABDAA
Örüntü : ABCD

Şöyle olur. Önceki A ve B harflerinde A ile başlama olmayacağını bildiğimiz için 2 harf atlayabiliriz.
Hedef  : ABDAA
Örüntü :      ABCD

3. D harfinde eşleşme olmasın.

3 - T[3] yani 3 -0 = 3 harf atlanır.

Hedef   : ABCEA
Örüntü : ABCD

Şöyle olur. Önceki A,B,C harflerinde A ile başlama olmayacağını bildiğimiz için 3 harf atlayabiliriz.

Hedef  : ABCEA
Örüntü :        ABCD

Örnek
Aradığımız string "ABCD" olsun. T tablosu şöyledir.
A  B  C  D
-1  0   0  0