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);
    }
}

function lcs($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);
    }
}


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

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


    for($i = 0; $i < $len_short; ++$i){
        for($j = $len_short; $j > 0; --$j){
            $needle = substr($shortest, $i, $j);
            $pos = strpos($longest, $needle);
            if($pos !== false) {
                break 2;
            }
        }
    }
    return substr($longest, $pos, strlen($needle));
}


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