最长公共子序列： Python, C++ 例如：

什么是最长公共子序列？

最长公共子序列 (LCS) 意味着您将获得两个字符串/模式/对象序列。在这两个序列/字符串中，您需要找到在两个字符串或模式中以相同顺序出现的元素的最长子序列。

例如：

例如，提供了两个字符串。

假设，

图案_1 = “RGBGARGA”
模式 2 = “BGRARG”

从 pattern_1 开始，可以生成类似“RGB”、“RGGA”、“RGAR”的序列。要创建序列，您需要维护字符串中每个字符的相对位置。
从 pattern_2 中，我们可以生成像“BGR”, ”BRAG”, ”RARG” 这样的序列。只要序列保持原始字符串的相对位置，就可以生成序列。

相对位置这个术语意味着顺序。

例如，“BRG” 是一个有效序列，因为在原始字符串 pattern_2 中，“B” 首先出现，然后是“R”，最后是“G”。但是，如果序列是“RBRG”，则它无效。因为在原始字符串 (pattern_2) 中，“B” 首先出现。

我们有两个选择可以从给定的两个序列或数组中找到最长公共子序列。

朴素方法
动态规划解决方案：最长公共子序列也称为LCS。

简单的解决方案具有较大的时间复杂度，并且不是最佳解决方案。使用动态规划解决方案（DP），我们克服了复杂性问题。

朴素方法

朴素方法是一种简单的解决问题的方法，无论时间复杂度和其他优化因素如何。

朴素方法在大多数情况下由“蛮力”、多重循环、递归方法组成。

术语“蛮力”是指针对给定问题尝试所有可能的模式。

例如：

从上面的 pattern1 和 pattern2 的例子来看，我们假设 pattern1 的长度为 m，pattern2 的长度为 n。为了检查每种可能的情况，我们需要用 pattern1 评估 pattern2 的每个可能子序列。

这是一个简单的 4 个字母的字符串“ABCD”。例如，我们需要从“ABCD”创建一个序列。我们可以取一个字符，也可以不取。这意味着，对于每个字符，我们有两个选择。

它们分别是：

该字符将被添加到子序列中。
该字符将不会添加到子序列中。

这里，图像显示了我们可以从字符串“ABCD”创建的所有序列。

包含 1 个字符的序列：

含有 2 个字符的序列：

含有 3 个字符的序列：

从上图可以看出，一共有 14 个序列。如果我们不取字母，基本上就是一个空字符串，那么总序列数将是 15。此外，字符串“ABCD”本身就是一个序列。因此，总序列数为 16。

因此，有可能生成 2⁴ 或“ABCD”中的 16 个子序列。然后，长度为 m 总子序列为 2^m.

对于每个子序列，我们需要检查整个模式2。这将花费0（n）的时间。0（n）表示计算执行所需时间的复杂性函数。

因此，总时间复杂度变为 O(n*2^m). 举例来说，我们上面看到 m=8 和 n=5 的值。

以下是朴素方法的步骤：

步骤1） 从模式1中取出一个序列。
步骤2） 将步骤 1 中的序列与模式 2 进行匹配。
步骤3） 如果匹配，则保存子序列。
步骤4） 如果模式1中还剩下更多序列，则再次转到步骤1。
步骤5） 打印最长子序列。

最优子结构

术语“最优子结构”表示可以通过解决子问题找到最优解（简单）。例如，在上面的例子中，我们有模式 1 和模式 2。

步骤1） 从每个模式中取出前两个字符

步骤2） 从每个模式中取出第三到第五个字符。

步骤3） 对其余字符继续进行类似操作。

我们在子字符串（由原始字符串生成的字符串）上找到 LCS。然后记录子字符串的 LCS 长度。

现在，这是另一个有趣的特性 重叠子问题如果问题陈述可以分解为小的子问题并且在程序中多次使用，则称该问题具有重叠子问题。

下图显示递归算法多次调用具有相同参数的函数。

例如，我们看一下递归树。

在深色框中，你可以注意到重叠的子问题。（“RG”，“RA”），（“RG”，“R”）和其他问题被调用了好几次。

为了优化这一点，我们采用了以下方法 动态编程 （DP）。

最长通信序列的递归方法

上图显示的是递归方法。每个递归函数都有一个基本情况来中断递归或开始从其堆栈返回。

对于此实现，我们将使用基本情况。因此，算法就像下面这样：

如果最后一个元素之前的所有元素都有匹配项，则将长度增加一并返回
将两个模式传递给函数，并取返回的最大值
如果一个模式的长度为零，则没有子序列可供比较。在这种情况下返回 0。这是递归的基本情况。

伪代码：

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
if len_1 or len_2 is zero:
    then
return 0
if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]
then
return 1 + lcs(pattern_1, pattern_2,
    len_1 - 1, len_2 - 1)
else
    max of lcs(pattern_1, pattern_2, len_1 - 1, len_2),
    lcs(pattern_1, pattern_2, len_1, len_2 - 1)

在实施 C++

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int lcs(string pattern_1, string pattern_2, int len_1, int len_2) {
  if (len_1 == 0 || len_2 == 0)
    return 0;
  if (pattern_1[len_1 - 1] == pattern_2[len_2 - 1]) {
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1);
  } else {
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1));
  }
}
int main() {
  string pattern_1, pattern_2;
  pattern_1 = "RGBGARGA";
  pattern_2 = "BGRARG";
  cout<<"Length of LCS is: "<<lcs(pattern_1, pattern_2, pattern_1.size(), pattern_2.size())<<endl;
}

输出：

Length of LCS is: 5

在 Python 中实现

def lcs(pattern_1, pattern_2, len_1, len_2):
    if len_1 == 0 or len_2 == 0:
    return 0
if pattern_1[len_1 - 1] == pattern_2[len_2 - 1]:
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
else :
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1))
pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Lenght of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

输出：

Lenght of LCS is:  5

最长公共子序列（LCS）的动态规划方法

动态规划意味着优化普通的递归方法。例如，如果我们查看递归或朴素方法图，我们可以看到有几个相同的函数调用。动态规划方法将所有计算记录在一个数组中，并在需要时使用它。

我们将使用尺寸为 mxn 的二维数组，其中 m 和 n 是 pattern2 和 pattern1 的长度。

对于二维阵列我们可以在 Python 中使用 List 数据结构，或者在 C++.

使用 DP 的 LCS 伪代码：

LCS(pattern_1, pattern_2):
    m = length of pattern_1 + 1
n = length of pattern_2 + 1
dp[n][m]
for i in range 0 to n + 1:
    for j in range 0 to m + 1:
    if i or j equals to 0:
    dp[i][j] = 0
else if pattern_1[i] == pattern_2[j]:
    dp[i]][j] = dp[i - 1][j - 1] + 1
else :
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[n][m]

这是用于动态规划方法的二维数组数据结构的表 LCS。

让我们讨论一下这里使用的逻辑。步骤如下：

步骤1） 如果 i 或 j 为零，我们将从给定的两个字符串中取出一个空字符串并尝试找到共同的子序列。但是，由于我们取的子字符串为空，因此子序列长度为 0。

步骤2） 如果两个字符匹配，我们将通过增加之前计算的 LCS 将值分配给 (i,j) 索引，该 LCS 存在于 (i-1,j-1) 索引（从上一行）。

步骤3） 如果不匹配，则取相邻两个索引中的最大LCS。这样，我们需要填充二维数组中的所有值。

步骤4） 最后，我们将返回二维数组最后一个单元格的值。

基本上，二维数组中的所有值都包含公共子序列的长度。其中，最后一个单元格包含最长公共子序列的长度。

在实施 C++

#include<iostream>
using namespace std;
int lcs(string pattern_1, string pattern_2) {
  int m = pattern_1.size();
  int n = pattern_2.size();
  // dp will store solutions as the iteration goes on
  int dp[n + 1][m + 1];
  for (int i = 0; i & lt; n + 1; i++) {
    for (int j = 0; j & lt; m + 1; j++) {
      if (i == 0 || j == 0) {
        dp[i][j] = 0;
      } else if (pattern_2[i - 1] == pattern_1[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[n][m];
}
int main() {
  string pattern_1 = "RGBGARGA";
  string pattern_2 = "BGRARG";
  cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;
}

输出：

Length of LCS: 5

在实施 Python

def lcs(pattern_1, pattern_2):
    m = len(pattern_1)
n = len(pattern_2)
# dp will store solutions as the iteration goes on
dp = [
    [None] * (n + 1) for item in range(m + 1)
]
for i in range(m + 1):
    for j in range(n + 1):
    if i == 0 or j == 0:
    dp[i][j] = 0
elif pattern_1[i - 1] == pattern_2[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]
pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS: ", lcs(pattern_1, pattern_2))

输出：

Length of LCS: 5

因此，两个字符串都有长度为 5 的最长公共子序列。

简而言之，在DP方法中，我们只是简单地计算一次DP方法中的每个任务。在递归方法中，我们可能会有重叠的子问题。

在这个动态规划算法中，我们使用一个二维矩阵。将给出两个字符串（假设两个字符串的长度均为 n）。那么数组中所需的空间为 nx n。如果字符串足够大，我们将需要一个内存优化版本的 DP 解决方案。

代码中采用的简化逻辑是：

声明一个二维数组DP[m][n]。
用0填充DP数组的第一行和第一列。
取i和j进行迭代。
如果 pattern1[i] 等于 pattern2[j]，则更新 DP[i][j] = DP[i-1][j-1] + 1
如果 pattern1[i] 不等于 pattern2[j]，则 DP[i][j] 将是 DP[i-1][j] 和 DP[i][j-1] 中的最大值。
继续，直到 i 和 j 达到 m 和 n。
最后一个元素或 DP[m-1][n-1] 将包含长度。

这里，它的寻址是 DP[m-1][n-1]，因为数组索引从 0 开始。

总结

DP方法的时间复杂度较低，为O(mn)，其中m和n是输入字符串或数组的长度。
DP 是一种比递归方法更快的方法，其时间复杂度为 O(n*2^m).
动态规划 (DP) 不是内存优化的。我们使用了长度为 m*n 的二维数组。因此，空间复杂度为 (m*n)。
递归方法，最坏的情况下它所占用的内存最高为m+n，基本就是输入字符串的总长度。
当今的现代计算机足以处理这种大小的内存。

你可能会喜欢：

什么是最长公共子序列？

例如：

朴素方法

例如：

最优子结构

相关文章

最长通信序列的递归方法

在实施 C++

在 Python 中实现

最长公共子序列（LCS）的动态规划方法

在实施 C++

在实施 Python

总结