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
}