当前位置：首页 > PHP

PHP实现了LCS

2026-02-16 21:24:31PHP

PHP实现LCS算法

LCS（最长公共子序列）算法用于查找两个序列之间的最长公共子序列。以下是PHP实现LCS的几种方法：

动态规划实现

动态规划是解决LCS问题的经典方法，通过构建二维数组记录子问题的解。

function lcs($str1, $str2) {
    $m = strlen($str1);
    $n = strlen($str2);
    $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));

    for ($i = 0; $i <= $m; $i++) {
        for ($j = 0; $j <= $n; $j++) {
            if ($i == 0 || $j == 0) {
                $dp[$i][$j] = 0;
            } elseif ($str1[$i - 1] == $str2[$j - 1]) {
                $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
            } else {
                $dp[$i][$j] = max($dp[$i - 1][$j], $dp[$i][$j - 1]);
            }
        }
    }

    return $dp[$m][$n];
}

递归实现

递归方法虽然简洁，但对于长字符串效率较低。

function lcsRecursive($str1, $str2, $m, $n) {
    if ($m == 0 || $n == 0) {
        return 0;
    }
    if ($str1[$m - 1] == $str2[$n - 1]) {
        return 1 + lcsRecursive($str1, $str2, $m - 1, $n - 1);
    } else {
        return max(
            lcsRecursive($str1, $str2, $m, $n - 1),
            lcsRecursive($str1, $str2, $m - 1, $n)
        );
    }
}

空间优化版本

通过仅保留当前行和上一行的数据来优化空间复杂度。

function lcsOptimized($str1, $str2) {
    $m = strlen($str1);
    $n = strlen($str2);
    $prev = array_fill(0, $n + 1, 0);
    $current = array_fill(0, $n + 1, 0);

    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            if ($str1[$i - 1] == $str2[$j - 1]) {
                $current[$j] = $prev[$j - 1] + 1;
            } else {
                $current[$j] = max($prev[$j], $current[$j - 1]);
            }
        }
        $prev = $current;
    }

    return $current[$n];
}

获取LCS字符串

上述方法仅返回长度，以下代码可返回实际的LCS字符串。

function getLcsString($str1, $str2) {
    $m = strlen($str1);
    $n = strlen($str2);
    $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));

    for ($i = 0; $i <= $m; $i++) {
        for ($j = 0; $j <= $n; $j++) {
            if ($i == 0 || $j == 0) {
                $dp[$i][$j] = 0;
            } elseif ($str1[$i - 1] == $str2[$j - 1]) {
                $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
            } else {
                $dp[$i][$j] = max($dp[$i - 1][$j], $dp[$i][$j - 1]);
            }
        }
    }

    $i = $m;
    $j = $n;
    $lcs = '';
    while ($i > 0 && $j > 0) {
        if ($str1[$i - 1] == $str2[$j - 1]) {
            $lcs = $str1[$i - 1] . $lcs;
            $i--;
            $j--;
        } elseif ($dp[$i - 1][$j] > $dp[$i][$j - 1]) {
            $i--;
        } else {
            $j--;
        }
    }

    return $lcs;
}