How to use the longest common subsequence algorithm in C++

How to use the longest common subsequence algorithm in C

The longest common subsequence (LCS) is a common string matching Problem to find the longest identical subsequence in two strings. In C, we can use dynamic programming (Dynamic Programming) to solve the LCS problem.

The following is a C code example that demonstrates how to use the longest common subsequence algorithm:

#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<int>> dp(m+1, vector<int>(n+1, 0));
    
    // 进行动态规划，填充数组
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // 如果当前字符相等，则在之前的基础上加1
            if (text1[i-1] == text2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                // 如果当前字符不相等，则取左边或上边的最大值
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    
    // 根据dp数组构建最长公共子序列
    int i = m;
    int j = n;
    string lcs = "";
    while (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 << "最长公共子序列为：" << lcs << endl;
    
    return 0;
}

In the above code, we first use dynamic programming to construct a two-dimensional arraydp , where dp[i][j] represents the first i characters of text1 and the first of text2 The length of the longest common subsequence composed of j characters. Then, we use the dp array to construct the longest common subsequence based on the results of dynamic programming. Finally, just output the longest common subsequence.

The above is an example of using the longest common subsequence algorithm in C. Through the idea of ​​dynamic programming, we can efficiently solve the LCS problem and find the longest common subsequence in two strings.

The above is the detailed content of How to use the longest common subsequence algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!