Algoritma Design Principle

 Algoritme Knuth-Morris-Pratt

Adalah salah satu algoritma pencarian string. Dikembangkan oleh secara terpisah oleh Donald E. Knuth pada tahun 1967 dan jammes H. Morris bersama Vaughan R. Pratt pada tahun 1996, Namun keduanya mempublikasikan secara bersama pada tahun 1077.

Jika kita melihat algoritma brute force lebih mendalam, kita mengetahui bawha dengan mengingat beberapa perbandingan yang dilakukan sebelumnya kita dapat meningkatakn besar pengeseran yang dilakukan. Hal ini akan menghemat perbandingan, yang selajutnya akan menginatkan kecepatan pencarian.

Cara kerja 

teks[i..i+j-1] = pattern [0..j-1] dan a = teks[i+j] tidak sama dengan b = pattern [j]. jika menggeser, sangat beralasan biala ada sebuah awalan v dari pattern akan sama dengan sebagian akhiran u dari sebagian teks. Sehingga kita bisa menggeser pattern agar awalan v tersebut sejajar dengan akhiran u.

Dengan kata lain. pencocokan string akan berjaalan dengan efisein bila kita mempunyai table yang menentukan berapa panjang seharusnya menggeser seandainya terindeksi ketidakcocokan dikarakter ke j  dari pattern. table itu harus memuat next [j]  yang merupakan posisi karakter pattern[j] setelah digeser, sehingga kita bisa menggeser pattern sebesar j-next[j] relatif terhadap teks.

secara sistematis, langkah-langkah yang dilakukan algoritma knuth--morris-pratt pada saat mencocokan string.

1.  Algoritme Knuth-Morris-Pratt mulai mencocokan pattern pada awal teks.
2. Dari kiri ke kanan, algoritma ini akan mencocokan karakter perkarakter pattern dengan karakter di teks yang bersesuaian, samapi salah satu kondisi berikut terpenuh (1) karakter dipattern dan di teks yang dibandingkan tidak cocok (mismatch), (2) semua karakter di pattern cocok. kemudian algoritma akan diberitahukan penemuan dipososi ini.
3. algoritma kemudian menggeser pattern berdasarkan table next, lalu mengulangi langkah-langkah samapi pattern berada diujung teks

procedure preKMP(
    input P: array[0..n-1] of char,
    input n: integer,
    input/output kmpNext: array[0..n] of integer
)
Deklarasi:
i,j: integer

Algoritme
  i:= 0;
  j:= kmpNext[0]:= -1;
  while (i < n) {
     while (j > -1 and not(P[i] = P[j]))
        j:= kmpNext[j];
     i:= i+1;
     j:= j+1;
     if (P[i] = P[j])
        kmpNext[i]:= kmpNext[j];
     else
        kmpNext[i]:= j;
     endif
  endwhile

Dan berikut adalah Pseudocode algoritme KMP pada pase pra-pencarian

procedure KMPSearch(
    input m, n: integer,
    input P: array[0..n-1] of char,
    input T: array[0..m-1] of char,
    output ketemu: array[0..m-1] of boolean
)

Deklarasi:
i, j,next: integer 
kmpNext: array[0..n] of interger

Algoritme:
preKMP(n, P, kmpNext) 
i:=0
while (i<= m-n) do
    j:=0
    while (j < n and T[i+j] = P[j]) do 
       j:=j+1
    endwhile
    if(j >= n) then
       ketemu[i]:=true;
    endif
    next:= j - kmpNext[j]
    i:= i+next
endwhile