怎样在PHP项目中实现最大公共子序列？

wen java案例 2026-07-19 174

本文目录导读：

怎样在PHP项目中实现最大公共子序列？

动态规划实现（推荐）
空间优化版本
递归实现（带记忆化）
完整的多子序列实现
性能测试和比较
实际应用示例

我来详细讲解如何在PHP中实现最大公共子序列（LCS）,包含多种方法和完整示例。

动态规划实现（推荐）

这是最经典的实现方式，时间复杂度 O(mn)：

<?php
function longestCommonSubsequenceDP($text1, $text2) {
    $m = strlen($text1);
    $n = strlen($text2);
    // 创建DP表
    $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
    // 填充DP表
    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            if ($text1[$i - 1] === $text2[$j - 1]) {
                $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
            } else {
                $dp[$i][$j] = max($dp[$i - 1][$j], $dp[$i][$j - 1]);
            }
        }
    }
    // 回溯找到LCS字符串
    $lcs = '';
    $i = $m;
    $j = $n;
    while ($i > 0 && $j > 0) {
        if ($text1[$i - 1] === $text2[$j - 1]) {
            $lcs = $text1[$i - 1] . $lcs;
            $i--;
            $j--;
        } else if ($dp[$i - 1][$j] > $dp[$i][$j - 1]) {
            $i--;
        } else {
            $j--;
        }
    }
    return [
        'length' => $dp[$m][$n],
        'sequence' => $lcs
    ];
}
// 使用示例
$text1 = "ABCDGH";
$text2 = "AEDFHR";
$result = longestCommonSubsequenceDP($text1, $text2);
echo "LCS长度: " . $result['length'] . "\n"; // 输出: 3
echo "LCS序列: " . $result['sequence'] . "\n"; // 输出: ADH
?>

空间优化版本

只保留两行数据,节省内存：

<?php
function longestCommonSubsequenceOptimized($text1, $text2) {
    $m = strlen($text1);
    $n = strlen($text2);
    // 只保留两行
    $prev = array_fill(0, $n + 1, 0);
    $curr = array_fill(0, $n + 1, 0);
    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            if ($text1[$i - 1] === $text2[$j - 1]) {
                $curr[$j] = $prev[$j - 1] + 1;
            } else {
                $curr[$j] = max($prev[$j], $curr[$j - 1]);
            }
        }
        // 交换数组
        list($prev, $curr) = [$curr, $prev];
    }
    return $prev[$n]; // 只返回长度
}
// 使用示例
$text1 = "AGGTAB";
$text2 = "GXTXAYB";
echo "LCS长度: " . longestCommonSubsequenceOptimized($text1, $text2) . "\n";
// 输出: 4
?>

递归实现（带记忆化）

<?php
function longestCommonSubsequenceRecursive($text1, $text2, $m, $n, &$memo = []) {
    // 基本情况
    if ($m === 0 || $n === 0) {
        return 0;
    }
    // 检查是否已计算
    $key = $m . ',' . $n;
    if (isset($memo[$key])) {
        return $memo[$key];
    }
    // 递归计算
    if ($text1[$m - 1] === $text2[$n - 1]) {
        $memo[$key] = 1 + longestCommonSubsequenceRecursive(
            $text1, $text2, $m - 1, $n - 1, $memo
        );
    } else {
        $memo[$key] = max(
            longestCommonSubsequenceRecursive($text1, $text2, $m - 1, $n, $memo),
            longestCommonSubsequenceRecursive($text1, $text2, $m, $n - 1, $memo)
        );
    }
    return $memo[$key];
}
// 使用示例
$text1 = "ABCBDAB";
$text2 = "BDCAB";
$m = strlen($text1);
$n = strlen($text2);
echo "LCS长度: " . longestCommonSubsequenceRecursive($text1, $text2, $m, $n) . "\n";
// 输出: 4
?>

完整的多子序列实现

返回所有可能的LCS：

<?php
class LCSFinder {
    private $dp = [];
    private $text1;
    private $text2;
    public function findAll($text1, $text2) {
        $this->text1 = $text1;
        $this->text2 = $text2;
        $m = strlen($text1);
        $n = strlen($text2);
        // 构建DP表
        $this->buildDP($m, $n);
        // 找出所有LCS
        $result = $this->backtrackAll($m, $n);
        // 去重并返回
        return [
            'length' => $this->dp[$m][$n],
            'sequences' => array_unique($result)
        ];
    }
    private function buildDP($m, $n) {
        $this->dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
        for ($i = 1; $i <= $m; $i++) {
            for ($j = 1; $j <= $n; $j++) {
                if ($this->text1[$i - 1] === $this->text2[$j - 1]) {
                    $this->dp[$i][$j] = $this->dp[$i - 1][$j - 1] + 1;
                } else {
                    $this->dp[$i][$j] = max(
                        $this->dp[$i - 1][$j], 
                        $this->dp[$i][$j - 1]
                    );
                }
            }
        }
    }
    private function backtrackAll($i, $j) {
        if ($i === 0 || $j === 0) {
            return [''];
        }
        if ($this->text1[$i - 1] === $this->text2[$j - 1]) {
            $subSequences = $this->backtrackAll($i - 1, $j - 1);
            return array_map(function($seq) use ($i) {
                return $seq . $this->text1[$i - 1];
            }, $subSequences);
        }
        $result = [];
        if ($this->dp[$i - 1][$j] >= $this->dp[$i][$j - 1]) {
            $result = array_merge($result, $this->backtrackAll($i - 1, $j));
        }
        if ($this->dp[$i][$j - 1] >= $this->dp[$i - 1][$j]) {
            $result = array_merge($result, $this->backtrackAll($i, $j - 1));
        }
        return $result;
    }
}
// 使用示例
$finder = new LCSFinder();
$text1 = "ABCBDAB";
$text2 = "BDCAB";
$result = $finder->findAll($text1, $text2);
echo "LCS长度: " . $result['length'] . "\n";
echo "所有LCS序列: \n";
foreach ($result['sequences'] as $seq) {
    echo "  - " . $seq . "\n";
}
?>

性能测试和比较

<?php
function performanceTest() {
    $testCases = [
        ['A', 'A'],
        ['ABCD', 'ABCD'],
        ['ABCD', 'DCBA'],
        ['AGGTAB', 'GXTXAYB'],
        ['ABCBDAB', 'BDCAB'],
        ['ACCGGTCGAGTGCGCGGAAGCCGGCCGAA', 'GTCGTTCGGAATGCCGTTGCTCTGTAAA']
    ];
    foreach ($testCases as $index => $test) {
        echo "测试用例 " . ($index + 1) . ":\n";
        echo "  字符串1: " . $test[0] . "\n";
        echo "  字符串2: " . $test[1] . "\n";
        // 方法1: DP完整实现
        $start = microtime(true);
        $result1 = longestCommonSubsequenceDP($test[0], $test[1]);
        $time1 = microtime(true) - $start;
        // 方法2: 优化版DP
        $start = microtime(true);
        $result2 = longestCommonSubsequenceOptimized($test[0], $test[1]);
        $time2 = microtime(true) - $start;
        echo "  完整DP: 长度={$result1['length']}, 序列='{$result1['sequence']}', 耗时={$time1}\n";
        echo "  优化版: 长度={$result2}, 耗时={$time2}\n\n";
    }
}
performanceTest();
?>

实际应用示例

<?php
class FileComparer {
    public function compareFiles($file1, $file2) {
        $content1 = file_get_contents($file1);
        $content2 = file_get_contents($file2);
        // 按行分割
        $lines1 = explode("\n", $content1);
        $lines2 = explode("\n", $content2);
        // 比较行序列
        $result = $this->findLCSLines($lines1, $lines2);
        return $result;
    }
    private function findLCSLines($lines1, $lines2) {
        $m = count($lines1);
        $n = count($lines2);
        $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
        for ($i = 1; $i <= $m; $i++) {
            for ($j = 1; $j <= $n; $j++) {
                if ($lines1[$i - 1] === $lines2[$j - 1]) {
                    $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
                } else {
                    $dp[$i][$j] = max($dp[$i - 1][$j], $dp[$i][$j - 1]);
                }
            }
        }
        // 生成差异报告
        $commonLines = [];
        $i = $m;
        $j = $n;
        while ($i > 0 && $j > 0) {
            if ($lines1[$i - 1] === $lines2[$j - 1]) {
                $commonLines[] = $lines1[$i - 1];
                $i--;
                $j--;
            } else if ($dp[$i - 1][$j] > $dp[$i][$j - 1]) {
                $i--;
            } else {
                $j--;
            }
        }
        return array_reverse($commonLines);
    }
}
// 使用示例
$comparer = new FileComparer();
$commonLines = $comparer->compareFiles('file1.txt', 'file2.txt');
echo "共同的行数: " . count($commonLines) . "\n";
echo "共同的内容:\n";
print_r($commonLines);
?>