Longest Common Substring algorithm in PHP

longest-common-substring.php

<?php

function getLongestCommonSubstring($first, $second)
{
    $longestCommonSubstringIndexInFirst = 0;
    $table = array();
    $largestFound = 0;

    $firstLength = strlen($first);
    $secondLength = strlen($second);
    for ($i = 0; $i < $firstLength; $i++) {
        for ($j = 0; $j < $secondLength; $j++) {
            if ($first[$i] === $second[$j]) {
                if (!isset($table[$i])) {
                    $table[$i] = array();
                }

                if ($i > 0 && $j > 0 && isset($table[$i-1][$j-1])) {
                    $table[$i][$j] = $table[$i-1][$j-1] + 1;
                }
                else {
                    $table[$i][$j] = 1;
                }

                if ($table[$i][$j] > $largestFound) {
                    $largestFound = $table[$i][$j];
                    $longestCommonSubstringIndexInFirst = $i - $largestFound + 1;
                }
            }
        }
    }
    if ($largestFound === 0) {
        return "";
    }
    else {
        return substr($first, $longestCommonSubstringIndexInFirst, $largestFound);
    }
}

echo getLongestCommonSubstring("aab", "baa") . PHP_EOL; // returns "aa"

This one is about 30% faster.

function lcs2($first, $second)
{
    $len1 = strlen($first);
    $len2 = strlen($second);

    if ($len1 < $len2) {
        $shortest = $first;
        $longest = $second;
        $len_shortest = $len1;
    } else {
        $shortest = $second;
        $longest = $first;
        $len_shortest = $len2;
    }
    
    //check max len
    $pos = strpos($longest, $shortest);
    if($pos !== false) return $shortest;

    for ($i = 1, $j = $len_shortest - 1; $j > 0; --$j, ++$i) {
        for($k = 0; $k <= $i; ++$k){
            $substr = substr($shortest, $k, $j);
            $pos = strpos($longest, $substr);
            if($pos !== false) return $substr;
        }
    }

    return "";
}

multibyte variant

function lcs2($first, $second)
{
    $len1 = strlen($first);
    $len2 = strlen($second);

    if ($len1 < $len2) {
        $shortest = $first;
        $longest = $second;
        $len_shortest = $len1;
    } else {
        $shortest = $second;
        $longest = $first;
        $len_shortest = $len2;
    }

    //check max len
    $pos = strpos($longest, $shortest);
    if($pos !== false) return $shortest;

    for ($i = 1, $j = $len_shortest - 1; $j > 0; --$j, ++$i) {
        for($k = 0; $k <= $i; ++$k){
            $substr = substr($shortest, $k, $j);
            $pos = strpos($longest, $substr);
            //if found then check last char if it is > 128 then trim it
            if($pos !== false) return ord($substr[$j-1]) > 128 ? substr($substr, 0, $j - 1) : $substr;
        }
    }

    return "";
}