LCS最长公共子序列

简介

LCS算法，即最长公共子序列（Longest Common Subsequence）算法，是一种在计算机科学中广泛应用的动态规划方法，用于找出两个或多个序列中共有的最长子序列。这里，“子序列”指的是原序列中字符保持原有相对顺序但不必连续出现的一段序列。请注意，最长公共子序列并不一定是唯一的。

应用领域

LCS算法的应用非常广泛，包括但不限于：

文件比较： 在软件版本控制中，用于比较文件差异。 生物信息学： 在基因序列分析中，用来识别不同个体或物种间的相似性。 文本处理： 在文本编辑器中实现“撤销”功能，或检测文档抄袭。 数据同步： 在数据库或数据流的同步中，确定数据的变更。

注意事项

• LCS问题求解的是子序列，不是子串，子序列中的字符不必连续。
• 解决方案可能不唯一，存在多个同样长度的最长公共子序列。
• 动态规划方法保证了在合理时间内获得最优解，但需注意空间复杂度管理。

示例PHP代码

<?php
/**
 * 获取两个字符串的最长公共子序列和相似度
 */
class LCS
{
    /** 
     * @var string $str1
     */
    public $str1;

    /**
     * @var string $str2
     */
    public $str2;

    /**
     * @var array $c
     */
    public $c = [];

    /**
     * 获取两个字符串的相似度
     * @param $str1
     * @param $str2
     * @return float
     */
    public function getSimilar($str1, $str2): float
    {
        $len1 = strlen($str1);
        $len2 = strlen($str2);
        $len = strlen($this->getLCS($str1, $str2, $len1, $len2));
        return round($len * 2 / ($len1 + $len2), 2);
    }

    /**
     * 获取最长公共子序列
     * @param $str1
     * @param $str2
     * @param int $len1
     * @param int $len2
     * @return string
     */
    public function getLCS($str1, $str2, int $len1 = 0, int $len2 = 0): string
    {
        $this->str1 = $str1;
        $this->str2 = $str2;

        if ($len1 === 0) {
            $len1 = strlen($this->str1);
        }

        if ($len2 === 0) {
            $len2 = strlen($this->str2);
        }

        $this->initC($len1, $len2);
        return $this->printLCS($len1 - 1, $len2 - 1);
    }

    /**
     * 输出最长公共子序列
     * @param $i
     * @param $j
     * @return string
     */
    public function printLCS($i, $j): string
    {
        if ($i == 0 || $j == 0) {
            if ($this->str1[$i] == $this->str2[$j]) {
                return $this->str2[$j];
            } else {
                return "";
            }
        }

        if ($this->str1[$i] == $this->str2[$j]) {
            return $this->printLCS($i - 1, $j - 1) . $this->str2[$j];

        } elseif ($this->c[$i-1][$j] >= $this->c[$i][$j-1]) {
            return $this->printLCS($i - 1, $j);

        } else {
            return $this->printLCS($i, $j - 1);
        }
    }

    /**
     * 初始化矩阵
     * @param $len1
     * @param $len2
     * @return void
     */
    public function initC($len1, $len2)
    {
        for ($i = 0; $i < $len1; $i++) {
            $this->c[$i][0] = 0;
        }

        for ($i = 0; $i < $len2; $i++) {
            $this->c[0][$i] = 0;
        }

        for ($i = 1; $i < $len1; $i++) {
            for ($j = 1; $j < $len2; $j++) {
                if ($this->str1[$i] == $this->str2[$j]) {
                    $this->c[$i][$j] = $this->c[$i-1][$j-1] + 1;

                } elseif ($this->c[$i-1][$j] >= $this->c[$i][$j-1]) {
                    $this->c[$i][$j] = $this->c[$i-1][$j];

                } else {
                    $this->c[$i][$j] = $this->c[$i][$j-1];
                }
            }
        }
    }
}