eXorithm – Execute Algorithm: View / Run Algorithm kmp_search

Logo Beta

function kmp_search ($x$y

{

  // see http://www-igm.univ-mlv.fr/~lecroq/string/node8.html

  

  // set-up phase

  $i = 0;

  $j = -1;

  

  $kmpNext = array();

  

  while ($i < $m) {

    while ($j > -1 && $x[i] != $x[j])

      $j = $kmpNext$j];

    $i++;

    $j++;

    if ($x$i] == $x$j])

      $kmpNext$i] = $kmpNext$j];

    else

      $kmpNext$i] = $j

  }

  

  // search phase

  $i = 0;

  $j = 0;

  $m = strlen$x);

  $n = strlen$y);

  

  $results = array();

  

  while ($j < $n) {

    while ($i > -1 && $x$i] != $y$j])

      $i = $kmpNext$i];

    $i++;

    $j++;

    if ($i >= $m) {

      $results[] = $j$i+1;

      $i = $kmpNext$i];

    }

  }

  

  return $results