Skip to content

Instantly share code, notes, and snippets.

@relaxnow

relaxnow/longest-common-substring.php

Created October 10, 2011 20:53
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save relaxnow/1276502 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save relaxnow/1276502 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. relaxnow created this gist Oct 10, 2011.
    40 changes: 40 additions & 0 deletions longest-common-substring.php
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,40 @@
    <?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"