Question

How to find the length of the longest common subsequence (LCS) in two strings with PHP

Answer 1

function mymax($a, $b) {
    return ($a > $b) ? $a : $b;
}
  
function lcs($s1, $s2, $s1_len, $s2_len) {
    if ($s1_len == 0 || $s2_len == 0) {
        return 0;
    }
    if ($s1[$s1_len - 1] == $s2[$s2_len - 1]) {
        return 1 + lcs($s1, $s2, $s1_len - 1, $s2_len - 1);
    }
    else {
        return mymax(lcs($s1, $s2, $s1_len, $s2_len - 1), lcs($s1, $s2, $s1_len - 1, $s2_len));
    }
}
   
   
$s1 = "accyrb";
$s2 = "cyxyazb";
 
echo "The length of LCS is: " . lcs($s1, $s2, strlen($s1), strlen($s2));
   

  
  
/*
run:
       
The length of LCS is: 3
      
*/

 

70+ SQL courses for beginners and professionals

Answer 2

/*
    This program computes BOTH:
      1. The length of the Longest Common Subsequence (LCS)
      2. The actual LCS subsequence

    It uses an efficient dynamic‑programming algorithm:
        Time:  O(n * m)
        Space: O(n * m)

    dp[i][j] stores the LCS length between:
        s1[0..i-1] and s2[0..j-1]

    Recurrence:
        If characters match:
            dp[i][j] = dp[i-1][j-1] + 1
        Else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    After filling the DP table, we reconstruct the LCS by
    walking backwards from dp[n][m].
*/

function lcs(string $s1, string $s2): array {
    $n = strlen($s1);
    $m = strlen($s2);

    // Create DP table initialized with zeros
    $dp = array_fill(0, $n + 1, array_fill(0, $m + 1, 0));

    // Fill DP table
    for ($i = 1; $i <= $n; $i++) {
        for ($j = 1; $j <= $m; $j++) {
            if ($s1[$i - 1] === $s2[$j - 1]) {
                $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
            } else {
                $dp[$i][$j] = max($dp[$i - 1][$j], $dp[$i][$j - 1]);
            }
        }
    }

    // Reconstruct the LCS sequence
    $length = $dp[$n][$m];
    $lcsChars = array_fill(0, $length, '');

    $i = $n;
    $j = $m;
    $index = $length - 1;

    while ($i > 0 && $j > 0) {
        if ($s1[$i - 1] === $s2[$j - 1]) {
            // Character is part of LCS
            $lcsChars[$index] = $s1[$i - 1];
            $index--;
            $i--;
            $j--;
        } elseif ($dp[$i - 1][$j] > $dp[$i][$j - 1]) {
            $i--; // Move up
        } else {
            $j--; // Move left
        }
    }

    $lcsString = implode('', $lcsChars);

    return [$length, $lcsString];
}

// Usage
$s1 = "AGGTAB";
$s2 = "GXTXAYB";

list($length, $sequence) = lcs($s1, $s2);

echo "String 1: $s1\n";
echo "String 2: $s2\n";
echo "Length of LCS: $length\n";
echo "LCS sequence: $sequence\n";


/*
run:

String 1: AGGTAB
String 2: GXTXAYB
Length of LCS: 4
LCS sequence: GTAB

*/

 

70+ SQL courses for beginners and professionals