Cara menggunakan algoritma urutan biasa terpanjang dalam C++

. Dalam C++, kita boleh menggunakan pengaturcaraan dinamik (Dynamic Programming) untuk menyelesaikan masalah LCS.

Berikut ialah contoh kod C++ yang menunjukkan cara menggunakan algoritma urutan sepunya terpanjang:

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

Dalam kod di atas, kami mula-mula menggunakan pengaturcaraan dinamik untuk membina tatasusunan dua dimensi

Tatasusunan membina urutan sepunya terpanjang. Akhir sekali, hanya keluarkan urutan biasa terpanjang.

Di atas ialah contoh menggunakan algoritma urutan lazim terpanjang dalam C++. Melalui idea pengaturcaraan dinamik, kami boleh menyelesaikan masalah LCS dengan cekap dan mencari urutan biasa terpanjang dalam dua rentetan.

Atas ialah kandungan terperinci Cara menggunakan algoritma urutan biasa terpanjang dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!