Modifikasi Core Algoritma Knuth-Morris-Pratt pada kmp.php - Elang Sakti
Download Ebook Belajar Arduino PDF, Arduino untuk pemula
Jasa Pembuatan Program Arduino, pemrograman Arduino
# Hack Your Skills! to be Professional Mechatronics

Modifikasi Core Algoritma Knuth-Morris-Pratt pada kmp.php

Tidak ada komentar
Solusi untuk pertanyaan mas adpermana, ada penambahan script isset() pada baris 27, 42, dan 65. Silakan dicek lagi, jika ada yang kurang pas, monggo kita diskusi lagi :).

<?php
// Knuth-Morris-Pratt Algorithm
// Created March 31, 2010 - 07:10:33 WIB
// Modified (again) April 13, 2013 - 06: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)){
      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;
  }
}
?>


Written by Hari Santoso
Modifikasi Core Algoritma Knuth-Morris-Pratt pada kmp.php
Bahasan: Solusi untuk pertanyaan mas adpermana, ada penambahan script isset() pada baris 27, 42, dan 65. Silakan dicek lagi, jika ada yang kurang p...
Published at Sabtu, 13 April 2013, Updated at Sabtu, 13 April 2013
Reviewed by dr. on
Rating: 4.7

Tidak ada komentar :

Poskan Komentar