Comment utiliser l'algorithme de sous-séquence commune la plus longue en C++

Comment utiliser l'algorithme de sous-séquence commune la plus longue en C++

La sous-séquence commune la plus longue (LCS) est un problème de correspondance de chaîne courant, utilisé pour trouver la plus longue de deux chaînes de la même sous-séquence. En C++, nous pouvons utiliser la programmation dynamique (Dynamic Programming) pour résoudre le problème LCS.

Ce qui suit est un exemple de code C++ qui montre comment utiliser l'algorithme de sous-séquence commune la plus longue :

#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;
}

Dans le code ci-dessus, nous utilisons d'abord la programmation dynamique pour construire un tableau bidimensionnel dp，其中dp[i][j]表示text1的前i个字符和text2的前j个字符所构成的最长公共子序列的长度。然后，我们根据动态规划的结果，利用dpLe tableau construit la sous-séquence commune la plus longue. Enfin, affichez simplement la sous-séquence commune la plus longue.

Ce qui précède est un exemple d'utilisation de l'algorithme de sous-séquence commune le plus long en C++. Grâce à l'idée de programmation dynamique, nous pouvons résoudre efficacement le problème LCS et trouver la sous-séquence commune la plus longue dans deux chaînes.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!