迹忆客 专注技术分享

在本文中，我们将讨论最长公共子串问题及其在 C++ 中使用动态规划的解决方案。

最长公共子串

最长公共子串（LCS）是计算机科学中的一个众所周知的问题。 两个或多个字符串中的最大长度子串是最长公共子串。

例如，考虑以下三个字符串：

1. XYXYZ
2. YXYZX
3. XYZYX

这三个字符串的最长公共子串是 XYZ。 这三个字符串中还存在其他公共子字符串，例如 X、XY、Y、YX、YZ 和 Z； 然而，最长的公共子串只是 XYZ。

图1展示了上述三个字符串的最长公共子串：

最长公共子串的问题表述

考虑两个长度分别为 m 和 n 的字符串 S1 和 S2，以从 S1 和 S2 中找到最大长度的确切子字符串。

我们将针对这个问题提出两种解决方案：

1. 一个简单的解决方案
2. 动态规划解决方案

一个简单的解决方案

以下是使用简单解决方案从两个字符串中查找最长公共子串的步骤：

• 查找第一个字符串 S1 的所有子字符串。
• 对于S1的每个子串，检查它是否是S2的子串。
• 请注意，最大长度子字符串与 S2 子字符串匹配。
• 由于字符串 S1 的长度为 m，因此有 $\mathcal{O}(m^2)$ 个子串。
• 字符串S2的长度为n，需要$\mathcal{O}(n)$来判断一个字符串是否是子串。
• 执行此解决方案所需的总时间复杂度为 $\mathcal{O}(nm^2)$。

该方案可以找到最长公共子串； 然而，这需要时间，所以让我们看看动态规划解决方案，以在更短的时间内实现相同的目标。

通过动态规划求最长公共子串

我们可以使用动态规划（DP）从两个字符串中找到最长公共子串（LCS）。 以下是使用动态规划方法查找最长公共子串的伪代码：

function Longest_Common_Substring(S1[1..m], S2[1..n])
    DP_Matrix = array(1..m, 1..n)
    len = 0
    result_substring = {}
    for i = 1..m
        for j = 1..n
            if S1[i] == S2[j]
                if i = 1 or j = 1
                    DP_Matrix[i, j] = 1
                else
                    DP_Matrix[i, j] = DP_Matrix[i − 1, j − 1] + 1
                if DP_Matrix[i, j] > len
                    len = DP_Matrix[i, j]
                    result_substring = {S1[i − len + 1..i]}
                else if DP_Matrix[i, j] == len
                    result_substring = result_substring ∪ {S1[i − len + 1..i]}
            else
                DP_Matrix[i, j] = 0
    return result_substring

上述解决方案需要二次（即 $\mathcal{O}(mn)$）时间复杂度来计算最长公共子串。 该解决方案是最优的并且始终保证最长的子匹配。

DP_Matrix 是一个二维数组或矩阵，用作动态编程表，用于存储前缀 S1[1..i] 和 S2[1..j] 的子串长度以及结束位置 S1[i] 和 S2[j]。

变量len用来存储目前为止找到的最大的result_substring长度。 子字符串用于存储长度为len的字符串。

DP_matrix 的第一行和第一列中的所有单元格都初始化为 1。使用目标函数来计算剩余的单元格。

该公式的目标函数可以表示为：

1. 对于给定单元格 DP_Matrix[i,j]，如果给定字符串序列的相应字符（即 S1[i] 和 S2[j] 处的字符）匹配，则我们将单元格 DP_Matrix[i-] 的值加 1 1，j-1]。

• 如果单元格 DP_Matrix[i,j] 的更新值大于之前的子字符串长度，则用这个新值更新 len。
• 同时，将此新的最大字符串保存到辅助字符串保持器（即 result_substring）。

1. 如果对应的字符不匹配（即不匹配的情况），则将单元格 DP_Matrix[i, j] 设置为零值，表示只能从这里开始新的子字符串。

在所有 M*N 次迭代之后（即 for 循环结束），result_substring 将具有最佳最大公共子串。

C++中的最长公共子串动态规划解决方案

以下代码用于使用 C++ 中的动态规划从字符串中查找最长公共子串。

#include <iostream>
#include <string>
using namespace std;

string Longest_Common_Substring (string Str1, string Str2)
{
  string result_substring = "";
  int m = Str1.length ();
  int n = Str2.length ();
  int DP_Matrix[m + 1][n + 1];
  int len = 0;
  int end = 0;

    for (int i = 0; i <= m; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            if (Str1[i] == Str2[j])
            {
                if ((i == 0) || (j == 0))
                    DP_Matrix[i][j] = 1;
                else
                    DP_Matrix[i][j] = 1 + DP_Matrix[i - 1][j - 1];

                if (DP_Matrix[i][j] > len)
                {
                    len = DP_Matrix[i][j];
                    int start = i - DP_Matrix[i][j] + 1;
                    if (end == start)
                    {
                           result_substring.push_back (Str1[i]);
                    }
                    else
                    {
                            end = start;
                            result_substring.clear ();
                            result_substring.append (Str1.substr (end, (i + 1) - end));
                    }
                }
           }
           else
           {
                DP_Matrix[i][j] = 0;
           }
        }
    }
   return result_substring;
}

int main ()
{
  string String1, String2;
  cout<<"Enter the first string: ";
  cin >> String1;
  cout<<"Enter the second string: ";
  cin >> String2;
  string substring=Longest_Common_Substring (String1, String2);
  cout << "LCS of " << String1 << " and " << String2 << " is " <<substring<< " of Length " << substring.length() <<endl;
  return 0;
}

上面的代码包含函数Longest_Common_Substring，它接受两个字符串（即String1和String2）作为参数，并返回它们的最佳最大公共子串。 Longest_Common_Substring函数使用动态规划表方法来查找该LCS。

在上面的代码中，DP_Matrix是一个二维整数数组，它存储字符串子对 S1[1..i] 和 S2[1..j] 的当前最佳子串长度。 正如伪代码解释中所讨论的，result_substring 用于存储找到的最长子字符串。

让我们看看上面代码对于不同字符串对的输出：

输出1：

Enter the first string: ATGCACATA
Enter the second string: GCAATGCACT
LCS of ATGCACATA and GCAATGCACT is ATGCAC of Length 6

输出2:

Enter the first string: ABCDDFA
Enter the second string: DCDDACDDF
LCS of ABCDDFA and DCDDACDDF is CDDF of Length 4

除了理论或数学证明之外，上述输出表明所讨论的动态规划解决方案是最优的。