C++에서 가장 긴 공통 부분 시퀀스 알고리즘을 사용하는 방법

C++에서 가장 긴 공통 부분 수열 알고리즘을 사용하는 방법

최장 공통 부분 수열(LCS)은 공통 문자열 일치 문제로, 두 문자열 중 동일한 부분 수열 중 가장 긴 것을 찾는 데 사용됩니다. C++에서는 동적 프로그래밍(동적 프로그래밍)을 사용하여 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<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;
}

위 코드에서는 먼저 동적 프로그래밍을 사용하여 2차원 배열을 만듭니다. dp，其中dp[i][j]表示text1的前i个字符和text2的前j个字符所构成的最长公共子序列的长度。然后，我们根据动态规划的结果，利用dp배열은 가장 긴 공통 부분 수열을 만듭니다. 마지막으로 가장 긴 공통 부분 수열을 출력합니다.

위는 C++에서 가장 긴 공통 부분 수열 알고리즘을 사용한 예입니다. 동적 프로그래밍 아이디어를 통해 우리는 LCS 문제를 효율적으로 풀고 두 문자열에서 가장 긴 공통 부분 수열을 찾을 수 있습니다.

위 내용은 C++에서 가장 긴 공통 부분 시퀀스 알고리즘을 사용하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!