eXorithm – Execute Algorithm: View / Run Algorithm kmp_search

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
}