<?php

// Knuth-Morris-Pratt strstr() function replacement.
// (c) Matous Jan Fialka, 2006. Licence: GNU/GPL.

// string length function

function str_len ($target)
{
        $i = -1;
        while (1)
        {
                $i += 1;
                if ($target[$i] == "")
                {
                        break;
                }
        }
        return $i;
}

// Knuth-Morris-Pratt failure function

function kmp_ffunc ($target)
{
        $t = 0;
        $m = str_len ($target);
        $f = array ();
        for ($s = 1; $s < $m; $s++)
        {
                while (($t > 0) && ($target[$s] != $target[$t]))
                {
                        $t = $f[$t];
                }
                if ($target[$t] == $target[$s])
                {
                        $t += 1;
                        $f[$s+1] = $t;
                } else {
                        $f[$s+1] = 0;
                }
        }
        return $f;
}

// Knuth-Morris-Pratt strstr() function replacement

function kmp_strstr ($src, $target)
{
        $s = 0;
        $m = str_len ($target);
        $t = str_len ($src);
        $f = kmp_ffunc ($target);
        for ($i = 0; $i < $t; $i++)
        {
                while (($s > 0) && ($src[$i] != $target[$s]))
                {
                        $s = $f[$s];
                }
                if ($src[$i] == $target[$s])
                {
                        $s += 1;
                }
                if ($s == $m)
                {
                        return ($i-$m+1);
                }
        }
        return FALSE;
}

// demo program

printf ("%d\n", kmp_strstr ("Matous Jan Fialka", "Jan"));

?>