kmp.php

<?php

function normalFind($a, $b){
    $matches = [];
    $lena = strlen($a);
    $lenb = strlen($b);
    for ($i=0; $i < strlen($a); $i++) {
        for ($j=0; $j < $lenb; $j++) { 
            if ($i + $j >= $lena) {
                break;
            }

            if ($b[$j] != $a[$i+$j]) {
                break;
            }
            if ($j + 1 == $lenb) {
                $matches[] = $i;
            }
        }
    }
    return $matches;
}


function getNext($str){
    $next[0] = 0;
    $len = strlen($str);
    $k = 0;
    for ($i = 1; $i < $len; $i++) { 
        while ($k > 0 && $str[$i]!=$str[$k]) {
            $k = $next[$k-1];
        }

        if ($str[$i] == $str[$k]){
            $k++;
        }
        $next[$i] = $k;
    }
    return $next;
}

function kmp($str, $find, $next){
    $matches = [];
    $lenStr = strlen($str);
    $lenFind = strlen($find);
    for ($i = 0, $j = 0; $i < $lenStr; $i++) {
        while ($j > 0 && $str[$i] != $find[$j]) {
            $j = $next[$j-1];
        }
        if ($str[$i] == $find[$j]) {
            $j++;
        }
        if ($j == $lenFind) {
            $matches[] = $i - $lenFind + 1;
            $j = 0;
        }
    }
    return $matches;
}



$a = "CBADADDDBBCADBBBACABADDBBBDBAACBABDAACCDDDDAABBBBDAADDDAADBDBADABBADADBADBCBDACDDCCAAABBAAAABDBBABDABDAABBBCABADCDAABDDACADDDBABBDDBDBABBACAACADDDADBACCAAACABDBDADBADACBACBDADCABBBDCABAAABBDBDAAAADDDCCDABAAAADDADCAABDABBDBDABDDDABCCDDDBDDDADAABCDAACAAAAABACBBBAAAAAAABAADBDDCCBADAAABBABBDBCDAAACADDDAADBABDADADACDDDBBDCABBBDBACAAABABABACBABDAADDDABCBCAABCDBBDADDCCDADDDCDCDAABABCDAABABDDDDADCDCDBDBABCDADBCDDAADBBDCBCDAABBDCCAABDDDDBDDABABADBBABCBBDDBDAAABDDDBABCDBAACABCBCCBBBABABBBDABDBAADDDDABCCDBBDABACCAABDACDDDDBAAADDADCCDDADBADBBDAABDCCDADDAAADCADBADDCDDBAAADABBCBDCBDAABDDAACDABDBDABCADBACADDADADDCBBACADBAAAADBACBBBBBDBBACBDBABDBDBBDAAABBDAACDDADBACCDABBAADABDDBABCBDDABADCAADBBDDDCBDBBAADDABDABDADCDCDCDAADDBBADDCCBABDDABBBCBAAABBBDBABBBABCCBADAABACCAABCABABDACCBDBBCBDBAADDABDABCADADBDCBDBAABAADDBAABDBAACAADBBBBAACADABABDDBDCABDBDADDABDCBABBDAABDADADBBABACABDDDCCDAACADACDBBDCBDADBDABADBBDACABBBDACDDBBDCACBCACBACBBADCBAABAABDACADDDBACABDDBBBABCBBDADABDADBCCBBDADCDABBDAABDCDDBDAAADCDBDDABCAADDDDBBABDBBADCAABDBDDBDACBDCADDABCCDBCDBACCBAAACAABAABADBDBABDDADCCBABABBBDABADCADADDBABADACDCADBDDABCADDABABADBDAAABACCBAABDDBACBBBDDDADDACBCDBAADDBBAAACDDBAAABBBDBCAACCBBAAADACDBABABACBBBBBADCCACBABAAAABCAAADAADABAAADBBBACBDDADDDBDCACBADBDBACAADCBCBCCDABDBDDDDDACBDDABDDACBCCADAABCBCCCBBDCADBCADADDBDCCBCBCBAAABAADBBAADBADADDDACDDAAABDBCBAABBACAADAAABBADAACADBBDDDBABADAACDBDDBBBCBDBABDAACAABBDDCCBABDBBBCDBBBADDBACDCBABBCABDBCCBDBDBDDCDBBAABBCBAACDADAAADDBDDDDBCAAACACACDBCBDADBCACABDDABBBBBDBBBCABBADABBDABDBAABADBAACDBCDCBCBBBADDAADCBDCCBDBCBBADDABDBABDBBCBDBDBBDAADADDDABBDAADDBDCACBAAABCBAAAAADDAACBCBCBCBDCDDAABCAAABBADCDDABDDDBBABDBDCBCBCCAADABABADBCDDCADBDBCDBDDBDDDBABBBCAADDCDBBADAAABDDADBDBDAAACBABACDAABDAADBABBACDBDBCBBAAADDDDBCABDBBACDBDCBBCBCADBAACBBCBCDCBABCADCADBCADADDADCBCCCBADDBBBBDABBBDDAADABCACBDCBBBDADAADABBADAADBABBBABAADBBABADDADADAABDABABBDACDDAACBBDDDDADBDAAACAACBBDBADDBCBBBBDDBADCABDCDDDDAABBABADADCDABAADBADBBADAABCDACBCBACCADAAADDDDADDDBBDBAADACDDDDDDDCABDDDADBDDADBCDBDBBBDDCABADCAAADCCBCAABDABCDBDBBDDBBADDADDDDABADADDABCBDBCDADAADDABBABBDCBBCADDDAACDAADBBDAABABBBAAACADDDBADCDCCBBAAABBDBABDACDCCCDCBDDADDAABBBCDCAAADCACAABBBBAADBCBCBBDDDBDDAADDCDABDDBBBADBBDDBBCDCADBDACBAABDAABABAAACBAABBACADDDDDACDAADBBADBABCCAABBDABADBABCBDABABABACBAACCDABAADBBCDDBBAADBBCCAAAADBAACBABDDBBBCDADBCABBDBCAAACDACADDADBDBBDDCABBCDBCBCCDDBADAADDBDABBBBBDCBDDBBBDBDAACBDBABABBBBDBBDDCCDADBBBCDADDCABAADDAADDDADDACDDDDBABBCBADBBADDBABCBDBBBACACBBCACAABBABDBAAABACABDDBDBDCBBAACCDDABDAAACABAACABABDADADBACAAADDDDCDBADBDDABBBBBCDBACAAABDCBBCBAAADCDCBACCDDBBDCDCDABDDABDCDCCCABCDACADDCDDDDDABBDABCBAABCDBBBBBBAADCDDBDBBCBDBDBCBDBDBBDABDBBDABBDDBABAADBDADBDDBAADBABBBCAAADDCCACCBCDDBACBBCDBADBDAADDDDDAAABCAADDADDCBAABACCBDBCDDDAADDBBBCDCADCBBDBBBBBADBBDBBAAAACDBDBAADDBBDBAADBCBDDAADCCDDCADBDCDCAABBDABADDBAABBDCCABBBAADDBDCBDDDAADAADDACBACBBBBDADDBBAABADACDBDDADABDABABCADDBAAADDADADDDADCBCCABDBADDCDAABDAAACBADDACADACAAABDDDABBAABABBBCBDAAAACACDBAADBACBBCCAAACDADDCDDCDADAAACABDADCBBBDACCDACCDBDBDCDCBDAABDBDBDABACAABDBBADBABAABDDADBAACDCBAABABDDDDADCAAACCBAABABCCDCCBBBCBBDBCBBBDABACADBDDAABDDABABAAADABADCACACCCAABADAAADBDBABABADDACBACDBBADDDAACBAAABABDABBDBDADBDDBCBDABBDACBDDAAABDBBDBBBABDDABBBADACBBBDBBDCABACBDBBDBCCACBBADDCDBADABABAABCACCBCDCBCAAACCCDDDADBDBBAAABBDABAADDDCDADABAADBDBDCABADDBABACDCABADBDBBDDDADCCDBBDDDBADACAABDBDABBDABAADABBCABADDAADADAADDCBADDAADBBBCACADAABCDBBDDBACBBACBADDAAABAADDABDDABCADBBDBCDBBAAADADBBACDDDBCAABDBABDBDBAADDACCDDBBDCBBADDBDBDBBCAAABCDBCCDABCCCCDDBAADACDCDCBDCBAADAADAADADBDBAABDBDBBCAAADDDABBDACCBDBACCACCDADBAAABBDDAABBADAABBBABCADDCDACBABBDBAAABCAADCDAACCACDBDCAADBDDDBACBDCBDDDCAABADBCBADABAABCABAAADABDBCBBBBDCABBCBCDADCABDADBBCABDAAADADBDABDBDBBBDBDADDACCCBDAAABCBADBBDABABBADCBDDACCDBDBCBDBDAADCBAACAADBBDABBADDAABDADDDADABDDAAACDBADCCCBBDBABDADAADADABCACDABBACDAACDBBADDBCCDDADDDADADAADCCADBBBDABDBBCABCACACABCDBDBABCACBCACBCCABDDDAABBCBDAABBBADBBABABBDBDAAAABDADDDAABCACDBCCBBBDDADDBACDDABCABBDBAAADDDBADBBAABACDBABAACDABDDDBBABDCAAAADACABABBADBDDABCBCABBDACDDDDDAAAACBDBBBBADADDDDDDBDABBDADAAAABBDBBAACBDDDAAABBADDAABBDADCDBACADBAACABDBACCDDBBDADCDDACDACACACABDBAAAABADBCABCBAAAABDDAACBBABBBBADADDCCADBCDBCDBDCDDBDBBBAADABBABDBBDBBDCDDAACDDBCBDADAABBBBDDCAADDAADBBBADCADBBCDDDDDAAADCBBBADCCABABDBBDDBADBCACABCDDCDDDCDCCBCCBACCADDBBAABAAAACDBDDBBDBCCADDDDBBCBCDABADCBDCDBDBACDDADDADADDABBDABDCBDADABDBDAADDDCDDCBBDCADABABDBACBBDBDCBBDADDAADACADACBDDDBABBBBBBBDDBCBDDDCCDDABADBDCBDADCBBCDCCBAACBADBBCBAAABACBBBAAACCAAADADBAADCBCCCCCDADACCCADDDBCDBBAADBDBADBCDBABDDCCBCDDCDDDDDDBDAACDBBBDDCBDAAABAAABBABBABCCAACCDCCDCDAADBDABBDACADDABAABABADDAAADCCCADCDDABBBADCBADACDBBDDADABBBDCDBBBBBDCBDCDADCBDBDBBAAABDDBADBABBADAACCBBDABADABAABBACBABBBABBCAADDDDDCDAAADAAABDBCBABCBACBDCABADBADCABADBDDABDCADCCDBABDDBBADDAAABBADBDCDCAABDABAAADDCDADBADBBDADCDACABABBBABABDBAACBADBBDDDBBBCAAADDBACDBCBDBCACCACABDBDCAACDBAAADADBBDBCACAADDADDDDBBBBBBBABCDDDBBDBDACDACDBBBAADDBAABADDADCDBBDADDDADCACDCAACBBAACCABDABADDACBACBBABADADBACDCDDABDBAAADAACAAABBACABBDABDABDBDCCBBBDBDBDBBBCABABBBCDADADDDADBDADCBBDCBDBABABCDBBCACCACDDADBCAADAABACDCDCBBBBDADCBDBDBDDBAABBBBCBCBCDBAADACCAAADDDBAABDABACBBAADDCDCABDAACDBADBBDDDDBCDCCDCBBDDBAABBCCCCADDDDBADADDABCBDBADBBBBBBBDBCCDDAADDDCDAADBADAAABDDCAACDBAABBBCDBDBBBABAADBBCBBDDDBCACADABAAABBBAABDBDDBCBAAADDDDAAADAABDDCCCDDACAACBCACDADBDABCBBABADBDABBABBCDDABBADBDDDDDADAABCBCAABADABABDDDBBCCBACCDABAACBCAADABBAABADBDAAAACDAACABBBBCDABBBCCACADAACCCBCCADCCDBDBBDBDBDABBBDAAADDAACDABBBDACBDCDDBCBABAAAACBDDDDBDAACDBABCDCCAACDBCBBBBCBDCDDBCCCABBCBBAADADDBBBBCAABDDDDDDBBCBBDAADBBBBCBBDDCDDCDDBBBBBBDBDCCDDBDDDDACADADDBBDBCDBABBCCBCABADABDDBDBDBBACDCACBAAABBCADCDDBACCCBBBDAAADBDCDADABCCDBACBABBCBAABDAABADBBDBBCCBACACADAAABDDBCAAAADDDDBACDDBCDCDDCDCBBACBDAABDACDCDAAABDADAAACADAADBDBBDAABBAABBDBACBAABCBACCCDADDBDBBCADAADCADCAAABADCDBDBDAAADACDAAAABDBDDAADBACBABDDDABDDBAABDDDDDDDCDABACABADABBBBDBDDABDDBCAABBBAAADCBDDAAACADBAABDDDDBDDBDABDCABDACBBACDBDAAABADACDDDDADBACDACABCDCBDBADBBBDBADDADBCADBBDADBCDDABCDBBDCBBCABBBBCACABBDDAADDBDBAABABADBBDBBADDABBDADCBDBBDDDBBBDBBBBBDBBBAABCABCBBDADBADBCCCABDCBDBAABBDDCDDBCABBBBBBDCDADBBACBCBBCBADDBDBAACAACBAADCBACBCBADCBDCDABAADBCDCBDABDDBBADDBDABBCAADBACDBACAABBDBABDDDADAAACDBDBDDDDBAACBBDAAAAACBBDBDDDDBCAAADBDCBABAACAABADABAACDABADCADDBBDABDDDACCDBABDACDAAABDBDDCBDBACDDBDCBDDBBABBCBACBBBCCCADBADDAAABCBDCABABABBBBADBDDBCBDDDBBABBDAABABAADBDBDADCBADBABBDADADBCABDDBCBABBCABACAADADBBDCDBDBAADACADCBABCDADACDADBCBCBDBADABBBACBBDDCDCABDDAADCBDBBDCADDAABBBADCADCDBDADCDCBCAADCBAADBBABCADDDDDBBBBBACCCCDCACCCBADCAAAAADADCDDAABBDDBABBDBDCBADDDBABCDABDAACDCBCBDCBDCBDDBBCDBCCCCABACABABACDADBBAACACDDADABACBDDADBDCDBBBCDBBCBABBCABCCBBDBCDDCABADDADDBDABDDABCDDDABCACDADADBBDCDABBABBBDCACAABDABBADDDDCADBBDBDACDBABDBABCDADCABBBAADAAABAADDCDABDCBDDDDAABDADBADCBDADDBBDCBADBADCABABABBADCBDDDABABDDACBBBDABBABBBBBABBBBDADADDBCDCCBCDDDCACCBCBCABDBBABDDCBACBCBCDDDCBADABDADDBCADDCDBADCDDBBDCACDBBADBDBDBCACBBDAADBDACABBAAACDBBDCADAAACBBBAADCADDDDBABABACDBDCCAAABCDDBDAAADBBDAACAAACAABCABBDACAADDACDDDCBBAADCAAAAABCACBCDDBBCBDADBADBABABCDDBDADDCDDDDDADDBDDDACDDBDADDACBDCCABCBBABBADDBDCAADBADCDACDDBADDDDBBAAADABABAACDBBDABDDAABAADCAADBBDDCACABCDBDDBDAABAABBBBADBAAAADBCABADBDDABBDADBADBABCBCBAACCBABBAAADBDBDCDCBBACABBDDDAABCDDBBDADCABACDBBDDADDABDDBBBADDDBBDCDCDABBDDCDACDBBBAAABDBACADCBBCDDABDABBAABCBDCDBCDDADCAABDDDCADDDABBCBCBBDBBBBADDACBAADCACBADABABADBBABDCDBABDADCBAADAABDBAAADCAADDBADCADADDADAADCDACDBBDCBAABAADBBDBABDDDDDABDBBBADADCDBCDBAADDCADBDAAAABBCDBBDDDADAABABDDDBDABBDBDBAAAACBCBBAACBBADBAAABDAABDDDDACACBCDDDABABADBDDBBADABCDBBAAADDBBAABBCCBADDABDACDDCBDBADABAACABABCBCADDBBAACABABADABBACADBBDBACBADDBBBABDADDDDDBDABCDACBBDBAAAAACDBBBDCCDDADBADCCABDDBBDABADABDADCCDAACBADDBCBABDDDCADADCABCABDABABBDCBBDABBDDADDDDDABDCBDDCDCDBAACBBBDCDBCDBBBABCDCADBCDAADDDDDABAAADBBBCDBBDBAADBAADBBDCAACCCABBDDABDADCCDDBDDCDBCDDACABAAABADADDDDBAADBAAADBDCBADABDABCBDDDDCCCDAACDDABACDAABABCCADBBADCCBAADDADABBCABBCADCBBBDACCBBBBBBBDBAAAADCBABCCDBADBCDADAAABDBDDABACABDBDDADADDBAAADDBBCDBBDCABDDCDBBCBAADBABBDDDACBDCDBCACDADCABCBBCDBADADBDABAABDCACBCBBACABDDBABDBDADDDBBABBABCAAABBAADBDDCABDAAAADBDADDDBDAAAADCDCADBACDCDDBAAACDBDBAAAAADABCAADBDCBAADCACABBBADDDAABABDDBDAAACBDDDDDACBBBBBBBAABCCDDBDDADADBBBACADADDADBABCDCADBDBBDCABBDDCBABCDBDDABBDBABDBDBABBAADAABBCBCCBDBADBDAABBBBDDADACADCADDAACDADBDABBADBADDBABAAAADCDBABBADAACCBDDDCBDACBAADDDADAAABBAACDBCADABBDAABBDBCCABACDDBADDBBDBBCBDDBADAACCBDCDBAAAADDAAAAABDBCBABBBDDDBBDDDBCCCBCBABDADBBADBCDDCDDADBBCDCBDCBBDDDDCCDCAAACDAADBDDDDADABDCADCAABCDDADCAADABBCCDBBBDDADCCDBABCDBAABCADABBDADCBABCABBADAABCBBDABBABDBADCAAADABBAAABDACDADADABDADADCBCACABBBBABADDDBCDDBCDDDBDAABDACBABDCBBBDCDBDDBCAADBAABAACDDCAABBBCAADBAADDADBBCCDBBDBDAADDBBDDABDDDABCCDCDBBCBBDCACCAADBCBABDABADADAABBBDABCACACAABABBBBCBCDDABBABADACBADACDBDBDCBCBCDABDADBAAADBBDCBDDCBDCDBDBDBABBDDABADADBDBCDBACDAABAADDBBCDADBBCCBDBABBDBBDDADAADDCBBBCBBDDADBBCACADBBBAAABDDADABBAABBBDDBCAADACBACCBACBDABCDBCDDAABACCDBDBBBBBBCDBADBCDCDBBABDDCCBBDABBADDCBCDDBDCBABBCDBACADBCABDCABCBCDAACCBCBADBBADADCABACADBCCDCAACBBABBDAAADDBBACBDABBABBAAAAABDACABABBCBABDAAAABBBABAAAACBCADCAACDABDDDADBABAADCBCABCADDAADDBDBBAABDDBBBADDAABDAABBDADBCBBBAAACDDAACCAADDCDBAADABCABDDDBBDACAADABBDADBADBBCDDBADDACDBBBBBBCBCDDAAACCBBAABDCABCBAADBADDDDACBBAADACDDAABAAAABCDDBBDBABDBCCBBDDDBCDDDBADDDBCDDADDACDBABCDDBDDADBCCBABDCDBDCBBBBBBABCDADAADADADADCAACDAAAAAADBDBBCDADDACDDDBAADBACBBBABDBBADBABABACBDAABDDBAABADDADCAAADBBDCDCBAABABDDCBBADBBBBBBBBBADDBAADBAABBCDAABAABADADABDBCACCCDDBDBCADBBDAADDAADCAAACCDCBBBBBDDACDDBDBDDABBADBBCBABBCAADAADBABABCDDBDCBDCDDDACBDCCDDBDBBDCDBBCDBDACBDCADBCABAADADBDCBCBCDABCABABBBBAADDAADBADCBACDBDABDADDDABADBBBDDBDADCDBDDBBACDABBDCADBBBADBBBDBBDBDDDABABDBBDDBADCADAADBBBCACADDDAADAADBABDABBABCCADCDCCBAABDABBCDACDCABADDCAABDCADDDBCCABDDCCADCABABCDADDAAAAABBDDCBBBCBCCDBBCBBABDBBDAAAAABBABBCBCBDBADBAAADCDDBCAABDDBDCDAABADBABABDCBBAADCABDDDCBDDBCDDBCDADDCCBACCBADACCCDBAAADBADACBBAABDBADADBDABBBCBABBDDBBBBCAAABCCCAABDDCDBBDDDDBDABBABBCBDDDBDABBCBA";
$b = "ABCDABD";


$repeat = 1000;

$tm1 = microtime(true);
for ($i = 0; $i < $repeat; $i++) { 
    $matches = normalFind($a, $b);
}


$tm2 = microtime(true);
for ($i = 0; $i < $repeat; $i++) { 
    $next = getNext($b);
    $matches = kmp($a, $b, $next);
}
$tm3 = microtime(true);


$total1 = $tm2-$tm1;
$total2 = $tm3-$tm2;

printf("t1: %s\nt2: %s\n", $total1, $total2);