Knuth-Morris-Pratt-Algorithm

kmp_match.php

<?php
/**
 * This is an implementation of the Knuth-Morris-Pratt-Algorithm as in
 * Thomas H. Cormen et. al.: "Algorithmen - Eine Einführung"
 * (German version by Paul Molitor) 3. Auflage, page 1017
 *
 * My changes:
 * - Indexes starting with 0
 * - overlapping matches are recognized
 */

function usage($argv)
{
    return 'usage: ' . $argv[0] . ' <Pattern> [Text]' . PHP_EOL;
}

function compute_prefix($P)
{
    $m = strlen($P);
    $pi = array();
    $pi[1] = 0;
    $k = 0;

    for ($q = 1; $q < $m; $q++) {
        while ($k > 0 && $P[$k] != $P[$q]) {
            $k = $pi[$k];
        }
        if ($P[$k] == $P[$q]) {
            $k = $k + 1;
        }
        $pi[$q+1] = $k;
    }

    return $pi;
}

function match($T, $P)
{
    $n = strlen($T);
    $m = strlen($P);
    $pi = compute_prefix($P);

    $q = 0;
    $l = 0;

    for ($i = 0; $i < $n; $i++) {
        while ($q > 0 && $P[$q] != $T[$i]) {
            $q = $pi[$q];
        }

        if ($P[$q] == $T[$i]) {
            $q = $q + 1;
        }

        if ($q == $m) {
            echo 'The Pattern occures at shift: ' . ($i - $m + 1) . '.' . PHP_EOL;
            if ($i-$m < $l) {
                echo 'The last two matches (' . ($l - $m + 1) . ' and ' . ($i - $m + 1) . ') are ' .
                     'overlapping.' . PHP_EOL;
            }
            $l = $i;
            $q = $pi[$q];
        }
    }
}

if (isset($argv[1])) {
    $P = $argv[1];

    if (isset($argv[2])) {
        $T = $argv[2];

        match($T, $P);
    } else {
        $pi = compute_prefix($P);

        foreach ($pi as $a => $b) {
            echo 'π(' . $a . ') = ' . $b . PHP_EOL;
        }
    }
} else {
    echo usage($argv);
    return;
}