Algoritma Knuth-Morris-Pratt (KMP)

Algoritma Knuth-Morris-Pratt dikembangkan secara terpisah oleh Donald E. Knuth pada tahun 1967 dan James H. Morris bersama Vaughan R. Pratt pada tahun 1966, namun keduanya mempublikasikannya secara bersamaan pada tahun 1977.

Algoritma Knuth-Morris-Pratt (KMP) merupakan algoritma yang digunakan untuk melakukan proses pencocokan string. Algoritma ini merupakan jenis Exact String Matching Algorithm yang merupakan pencocokan string secara tepat dengan susunan karakter dalam string yang dicocokkan memiliki jumlah maupun urutan karakter dalam string yang sama.

Contoh : kata ‘algoritma’ akan menunjukkan kecocokan hanya dengan kata ‘algoritma’. Pada algoritma Knuth-Morris-Pratt (KMP), kita simpan informasi yang digunakan untuk melakukan pergeseran lebih jauh, tidak hanya satu karakter seperti algoritma Brute Force. Algoritma ini melakukan pencocokan dari kiri ke kanan.

Terdapat beberapa definisi pada algoritma Knuth-Morris-Pratt (KMP) :

1.       Misalkan A adalah alfabet dan x = x1x2…xk adalah string yang panjangnya k yang dibentuk dari karakterkarakter di dalam alfabet A.

• Awalan (prefix) dari x adalah upa-string (substring) u dengan u = x1x2…xk – 1 , k ϵ {1, 2, …, k –1}dengan kata lain, x diawali dengan u.

• Akhiran (suffix) dari x adalah upa-string (substring) u dengan u = xk – b xk – b + 1 …xk , k ϵ {1, 2, …, k– 1}dengan kata lain, x di akhiri dengan v

• Pinggiran (border) dari x adalah upa-string r sedemikian sehingga r = x1x2…xk – 1 dan u=xk–bxk – b + 1 …xk , k ϵ {1, 2, …, k –1}, dengan kata lain, pinggiran dari x adalah upa-string yang keduanya awalan dan juga akhiran sebenarnya dari x.

2.       Fungsi Pinggiran b(j) didefinisikan sebagai ukuran awalan terpanjang dari P yang merupakan akhiran dari P[1..j].

pseudo code : (KLIK UNTUK MEMPERBESAR)