PHP : Modifikasi Class Algoritma KMP Untuk Replace String - Elang Sakti
Download Ebook Belajar Arduino PDF, Arduino untuk pemula
Jasa Pembuatan Program Arduino, pemrograman Arduino
# Hack Your Skills! to be Professional Mechatronics

PHP : Modifikasi Class Algoritma KMP Untuk Replace String

2 komentar
Kali ini kita akan membahas tentang replace string pada PHP dengan bantuan algoritma string matching KMP (Knuth-Morris-Pratt).

Pada tulisan Algoritma Pencocokan / Pencarian String dengan Knuth-Morris-Pratt Menggunakan PHP kita sudah belajar membuat core dari Algoritma KMP dengan bahasa PHP. Kini kita akan menambahkan fungsi replace string setelah menemukan kata yang cocok. Pada artikel Implementasi Algoritma String Matching Knuth-Morris-Pratt Menggunakan PHP (1) kita sudah mengetahui posisi string kata pada teks. Akan tetapi untuk mereplace string yang cocok, pada script tersebut masih menggunakan bawaan PHP yaitu str_replace(). Kini kita akan membuat fungsi replace sendiri berdasarkan algoritma KMP.

Tambahan fungsi ini digunakan untuk memudahkan ketika kita ingin mengganti kata yang cocok menjadi kata yang kita inginkan. Untuk penggunaannya, setelah kita membuat instance dari kelas KMP, kita tinggal memanggilnya dengan perintah KMP->KMPReplace(string_awal, string_pengganti, $teks).


<?php
// Knuth-Morris-Pratt Algorithm
// Created March 31, 2010 - 07:10:33 WIB
// Modified (again) March 16, 2013 - 17:43:54 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)){
      while($i>-1 && $pattern[$i]!=$text[$j]){
     // jika tidak cocok, maka lompat sesuai tabel lompatan
        $i = $lompat[$i];
      }
      $i++;
      $j++;
      if($i>=count($pattern)){
     // jika cocok, tentukan posisi string yang cocok
  // kemudian lompat ke string berikutnya
        $hasil[$num++]=$j-count($pattern);
        $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($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;
  }
}
?>


Written by ElangSakti
PHP : Modifikasi Class Algoritma KMP Untuk Replace String
Bahasan: Kali ini kita akan membahas tentang replace string pada PHP dengan bantuan algoritma string matching KMP (Knuth-Morris-Pratt). Pada tu...
Published at Minggu, 17 Maret 2013, Updated at Minggu, 17 Maret 2013
Reviewed by dr. on
Rating: 4.7

2 komentar :

  1. sourcode algoritma Aho Corasick ada om? sama seperti diatas kasusnya pencocokan kata kunci juga

    BalasHapus
  2. sourcode algoritma aho corasick ada min? Kasusnya sama persis

    BalasHapus