C++ 代码:动态规划法求解最长公共子序列 (LCS) 及其时间空间复杂度分析
注:本代码采用 LCS(最长公共子序列)算法,时间复杂度为 O(mn),空间复杂度为 O(mn),其中 m 和 n 分别为两个字符串的长度。
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
string s1, s2;
ifstream fin('input.txt'); // 从文件中读取输入字符串
fin >> s1 >> s2;
fin.close();
int len1 = s1.size(), len2 = s2.size();
vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1)); // 二维矩阵 dp,用于存储 LCS 长度
for (int i = 1; i <= len1; i++)
{
for (int j = 1; j <= len2; j++)
{
if (s1[i - 1] == s2[j - 1]) // 当前字符相等
{
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else // 当前字符不相等
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
cout << '生成的二维矩阵为:' << endl;
for (int i = 0; i <= len1; i++)
{
for (int j = 0; j <= len2; j++)
{
cout << dp[i][j] << ' ';
}
cout << endl;
}
cout << '所有的最长公共子序列为:' << endl;
vector<char> res; // 存储最长公共子序列
int i = len1, j = len2;
while (i > 0 && j > 0)
{
if (s1[i - 1] == s2[j - 1])
{
res.push_back(s1[i - 1]);
i--;
j--;
}
else if (dp[i - 1][j] >= dp[i][j - 1])
{
i--;
}
else
{
j--;
}
}
reverse(res.begin(), res.end()); // 由于是从后往前加入 res 的,所以需要翻转一下
for (char c : res)
{
cout << c << ' ';
}
return 0;
}
注解如下:
-
头文件包含了 iostream、fstream、string、vector 和 algorithm。其中,iostream 和 fstream 用于文件输入输出,string 用于处理字符串,vector 用于存储二维矩阵 dp,algorithm 用于 reverse 函数的调用。
-
main 函数中,首先定义了两个字符串 s1 和 s2,并通过 ifstream 从文件中读取输入字符串。然后,求出两个字符串的长度 len1 和 len2,并定义了一个二维矩阵 dp,用于存储 LCS 长度。
-
通过双重循环遍历两个字符串的所有字符,如果当前字符相等,则在 dp[i][j] 中加上 dp[i-1][j-1]+1 的长度。如果当前字符不相等,则取 dp[i-1][j] 和 dp[i][j-1] 的最大值。
-
输出生成的二维矩阵 dp。
-
通过双指针 i 和 j,从后往前遍历 dp 数组,将最长公共子序列存储在 res 数组中。当 s1[i-1] 等于 s2[j-1] 时,将当前字符加入 res 数组中,i 和 j 都减 1。当 dp[i-1][j] 大于等于 dp[i][j-1] 时,i 减 1。否则,j 减 1。
-
最后,将 res 数组中的字符输出即可。
-
时间复杂度为 O(mn),其中 m 和 n 分别为两个字符串的长度。空间复杂度为 O(mn),因为需要存储一个二维矩阵 dp。
原文地址: https://www.cveoy.top/t/topic/or34 著作权归作者所有。请勿转载和采集!