注:本代码采用 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;
}

注解如下:

  1. 头文件包含了 iostream、fstream、string、vector 和 algorithm。其中,iostream 和 fstream 用于文件输入输出,string 用于处理字符串,vector 用于存储二维矩阵 dp,algorithm 用于 reverse 函数的调用。

  2. main 函数中,首先定义了两个字符串 s1 和 s2,并通过 ifstream 从文件中读取输入字符串。然后,求出两个字符串的长度 len1 和 len2,并定义了一个二维矩阵 dp,用于存储 LCS 长度。

  3. 通过双重循环遍历两个字符串的所有字符,如果当前字符相等,则在 dp[i][j] 中加上 dp[i-1][j-1]+1 的长度。如果当前字符不相等,则取 dp[i-1][j] 和 dp[i][j-1] 的最大值。

  4. 输出生成的二维矩阵 dp。

  5. 通过双指针 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。

  6. 最后,将 res 数组中的字符输出即可。

  7. 时间复杂度为 O(mn),其中 m 和 n 分别为两个字符串的长度。空间复杂度为 O(mn),因为需要存储一个二维矩阵 dp。

C++ 代码:动态规划法求解最长公共子序列 (LCS) 及其时间空间复杂度分析

原文地址: https://www.cveoy.top/t/topic/or34 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录