本文目录导读：
我来详细讲解如何在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);
?>
- 推荐使用动态规划：时间复杂度O(mn)，空间复杂度O(mn)
- 内存优化：使用两行数组，空间复杂度降为O(min(m,n))
- 处理大数据：考虑使用文件流和分块处理
- 实际应用：文件比较、DNA序列分析、文本差异对比等
选择哪种实现取决于你的具体需求：
- 只需要长度：使用空间优化版本
- 需要具体序列：使用完整DP版本
- 需要所有可能序列：使用回溯版本
