Bezets

Software Engineer
User Avatar
I'm Available for work

KMP (Knuth-Morris-Pratt) Algorithm

7 May 2021 136 Views
AlgorithmPHP

Algoritma KMP (Knuth–Morris–Pratt) adalah salah satu algoritma yang dapat digunakan untuk mencari dimana sebuah string (dalam kasus ini dinamakan sebagai pola) apakah ditemukan di dalam kumpulan string lain dengan ukuran yang lebih besar.

Knuth–Morris–Pratt menggunakan pendekatan pengamatan bahwa ketika sebuah ketidakcocokan terjadi, data input tersebut akan mengambil informasi tertentu untuk menentukan dimanakah selanjutnya pencarian dilakukan, dengan demikian pengecekan dapat dilakukan secara tidak berurutan tetapi tetap akan melewati pengecekan string yang sudah dicek sebelumnya.

Langkah-langkah penggunaan algoritma ini adalah :

1. Tentukan Teks yang digunakan sebagai input

Contoh data input adalah sebagai berikut :

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Proin ut consectetur mi, sed rutrum arcu. Sed bibendum tortor sit amet mauris fermentum posuere. Donec vel rutrum velit. Pellentesque vulputate suscipit neque a auctor. Orci varius natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus.

2. Tentukan pola kunci yang digunakan dalam pencarian

Diasumsikan pola yang akan dicari adalah labor

3. Lakukan pencarian kata kunci menggunakan algoritma ini

// KMP (Knuth-Morris-Pratt) Code in PHP
// Variable $car adalah pattern yang akan dicari
// Variable $tex adalah inputnya
function KMP($car,$tex){
    //pemrosesan awal karakter pattern dengan function pecah($input)
    $cari = pecah($car);
    //hitung lebar pattern
    $lebarCari = count($cari);
    //pemrosesan awal karakter text dengan function pecah($input)
    $text = pecah($tex);
    //hitung lebar text
    $lebarText = count($text);
 
    //penentuan lebar lompatan jika karakter tidak cocok
    //lompat ini berbentuk array juga.
    $lompat = preKMP($cari);
 
    //proses pencocokan utama ada di sini...
    // $i untuk lompatan
    // $j lebar text
    $i = $j = 0;
    $num=0;
    while($j < $lebarText){
       //jika lompatan bernilai 0 keatas dan ada karakter yang tidak cocok
       //maka lompat sebanyak karakter yang ditentukan di preKMP tadi
       while($i > -1 && isset($cari[$i]) != $text[$j]){
           $i = $lompat[$i];
       }
       $i++;
       $j++;
 
       //jika pattern cocok dengan potongan text
       if($i >= $lebarCari){
           $i = $lompat[$i];
           $hasil[$num++] = $j - $lebarCari;
       }
    }
    return $hasil;
}
 
function preKMP($cari){
    //hitung lebar pattern
    $lebarCari = count($cari);
 
    //inisialisaasi awal
    $i = 0;
    $j = $lompat[0] = -1;
    //ulangi sebanyak lebar pattern
    //jadi pemrosesannya setiap karakter
    while($i < $lebarCari){
       //proses berikut akan lebih dipahami
       //jika dipadukan dengan teori yang sudah ada
       //so, read first..
       while($j > -1 && isset($cari[$i]) != isset($cari[$j])){
           $j = $lompat[$j];
       }
       $i++;
       $j++;
       
       if(isset($cari[$i]) == isset($cari[$j])){
           $lompat[$i] = $lompat[$j];
       }else{
           $lompat[$i] = $j;
       }
    }
    return $lompat;
}

function pecah($input){
  //perulangan sebanyak lebar input / banyak karakter
  for($h=0; $h < strlen($input); $h++){
    //text akan dibentuk menjadi array karakter
    //sehingga pemrosesannya lebih mudah.
    //misal $input = "haripinter";
    //maka $output dari proses ini yaitu
    //$output[0]='h';
    //$output[1]='a';
    //$output[2]='r';
    //$output[3]='i';
    //...hingga...
    //$output[9]='r';
    $output[$h] = substr($input, $h, 1);
  }
 
  //nilai $output ditransfer ke function pecah.
  return $output;
}
Contoh Penggunaan

$text = 'Lorem ipsum dolor sit amet, consectetur adipiscing elit. Proin ut consectetur mi, 
sed rutrum arcu. Sed bibendum tortor sit amet mauris fermentum posuere. 
Donec vel rutrum velit. Pellentesque vulputate suscipit neque a auctor. 
Orci varius natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus.

'; $cari = 'amet

'; echo 'Text input Adalah : "' . $text . '"
"'; echo 'Pola kata kunci adalah : "' . $cari . '"
"'; $hasil = KMP($cari, $text); echo "Posisi string yang cocok pada : "; for($s = 0; $s < count($hasil); $s++){ if($s > 0){ echo " dan ". $hasil[$s]; }else{ echo $hasil[$s]; } }

Hasilnya adalah