如何使用C++中的最长公共子序列算法

如何使用C++中的最长公共子序列算法

最长公共子序列（Longest Common Subsequence，简称LCS）是一种常见的字符串匹配问题，用于寻找两个字符串中最长的相同子序列。在C++中，我们可以使用动态规划（Dynamic Programming）来解决LCS问题。

下面是一个C++代码示例，演示了如何使用最长公共子序列算法：

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string longestCommonSubsequence(string text1, string text2) {
    int m = text1.size();
    int n = text2.size();
    
    // 创建一个二维数组来存储中间结果
    vector<vector>> dp(m+1, vector<int>(n+1, 0));
    
    // 进行动态规划，填充数组
    for (int i = 1; i  0 && j > 0) {
        if (text1[i-1] == text2[j-1]) {
            // 如果当前字符相等，则将字符加入最长公共子序列中
            lcs = text1[i-1] + lcs;
            i--;
            j--;
        } else {
            // 如果当前字符不相等，则根据dp数组移动指针
            if (dp[i-1][j] >= dp[i][j-1]) {
                i--;
            } else {
                j--;
            }
        }
    }
    
    return lcs;
}

int main() {
    string text1 = "ABCD";
    string text2 = "ACDF";
    
    string lcs = longestCommonSubsequence(text1, text2);
    
    cout <p>上述代码中，我们首先使用动态规划来构建一个二维数组<code>dp</code>，其中<code>dp[i][j]</code>表示<code>text1</code>的前<code>i</code>个字符和<code>text2</code>的前<code>j</code>个字符所构成的最长公共子序列的长度。然后，我们根据动态规划的结果，利用<code>dp</code>数组构建最长公共子序列。最后，输出最长公共子序列即可。</p>
<p>以上就是使用C++中的最长公共子序列算法的一个示例。通过动态规划的思想，我们可以高效地解决LCS问题，找到两个字符串中的最长公共子序列。</p></int></vector></string></vector></iostream>

C++免费学习笔记（深入）：立即学习
>在学习笔记中，你将探索 C++ 的入门与实战技巧！