fatkulnurk
12/4/2017 - 2:39 PM

## Algoritma Knuth-Morris-Pratt

Algoritma Knuth-Morris-Pratt

``````<?php
// Referensi :
// https://id.wikipedia.org/wiki/Algoritma_Knuth-Morris-Pratt
// https://stackoverflow.com/questions/44081348/is-it-possible-to-use-knuth-morris-pratt-algorithm-for-string-matching-on-text-t
// http://www.elangsakti.com/2013/03/implementasi-algoritma-string-matching.html
// https://stackoverflow.com/questions/29439930/knuth-morris-pratt-string-search-algorithm
// https://stackoverflow.com/questions/5873935/how-to-optimize-knuth-morris-pratt-string-matching-algorithm
// https://stackoverflow.com/questions/13271856/understanding-knuth-morris-pratt-algorithm
//
//
// Info Program
// Knuth-Morris-Pratt Algorithm
// Created March 31, 2010 - 07:10:33 WIB
// Modified (again) Nov 04, 2017 - 13:11:21 WIB
class KMP{
/* pencarian KMP
* input :
*   \$p = (string) pattern;
*   \$t = (string) teks;
* output :
*   \$hasil = (array int) posisi string pada teks
*/
function KMPSearch(\$p,\$t){
\$hasil = array();
// pattern dan text dijadikan array
\$pattern = str_split(\$p);
\$text    = str_split(\$t);

// hitung tabel lompatan dengan preKMP()
\$lompat = \$this->preKMP(\$pattern);
//print_r(\$lompat);

// perhitungan KMP
\$i = \$j = 0;
\$num=0;
while(\$j<count(\$text)){
if(isset(\$pattern[\$i]) && isset(\$lompat[\$i])){
while(\$i>-1 && \$pattern[\$i]!=\$text[\$j]){
// jika tidak cocok, maka lompat sesuai tabel lompatan
\$i = \$lompat[\$i];
}
}else{
\$i = 0;
}

\$i++;
\$j++;
if(\$i>=count(\$pattern)){
// jika cocok, tentukan posisi string yang cocok
// kemudian lompat ke string berikutnya
\$hasil[\$num++]=\$j-count(\$pattern);
if(isset(\$lompat[\$i])){
\$i = \$lompat[\$i];
}
}
}
return \$hasil;
}

/* menetukan tabel lompatan dengan preKMP
* input :
*   \$pattern = (string) pattern
* output :
*   \$lompat = (array int) untuk jumlah lompatan
*/
function preKMP(\$pattern){
\$i = 0;
\$j = \$lompat[0] = -1;
while(\$i<count(\$pattern)){
while(\$j>-1 && \$pattern[\$i]!=\$pattern[\$j]){
\$j = \$lompat[\$j];
}
\$i++;
\$j++;
if(isset(\$pattern[\$i])&&isset(\$pattern[\$j])){
if(\$pattern[\$i]==\$pattern[\$j]){
\$lompat[\$i]=\$lompat[\$j];
}else{
\$lompat[\$i]=\$j;
}
}
}
return \$lompat;
}

/* replace string
* input :
*   \$str1 = (array string) string yang akan diganti dengan str2
*   \$str2 = (array string) string yang akan mengganti str1
*   \$text = (string) text yang akan dicari
* output :
*   \$t = teks yang sudah difilter
*/
function KMPReplace(\$str1,\$str2,\$text){
\$num = 0;
\$location = \$this->KMPSearch(\$str1,\$text);
\$t = '';
\$n = 0; \$nn = 0;
foreach(\$location as \$in){
\$t .= substr(\$text,\$n+\$nn,\$in-\$n-\$nn).\$str2;
\$nn = strlen(\$str1);
\$n = \$in;
}
\$t .= substr(\$text,\$n+\$nn);
return \$t;
}
}

\$conn = mysqli_connect('localhost','root','','web');
\$kata = '';
if(isset(\$_GET['kata']))
\$kata = strtolower(\$_GET['kata']);

?>

<!-- form untuk inputan teks -->
<div style="width:600px;">
<form method="get" action="">
Cari Kata : <input type="text" name="kata" value="<?php echo \$kata; ?>" /> <input type="submit" value="Cari">
</form>
</div>

<?php
// Membuat object baru
\$KMP = new KMP();

\$art = \$conn->query('select * from ta');
while(\$teks = mysqli_fetch_array(\$art)){
strtolower(\$kata);
if(\$kata!=''){
\$hasil = \$KMP->KMPSearch(\$kata,\$teks['isi']);
echo "Kata yang dicari adalah : ".\$kata."<br/>";
echo "Jumlah kata yang ditemukan : ".count(\$hasil)."<br/>";
echo "Yaitu pada posisi string ke : ";
foreach(\$hasil as \$h) echo \$h." ";
echo "<br/>";
}
echo "<div style='width:600px;'>";
echo "<h3>".\$teks['judul']."</h3><hr/>";
echo nl2br(str_replace(\$kata,"<font color='red'><b>".\$kata."</b></font>",\$teks['isi']));
echo "</div>";
}
?>
``````