Heim  >  Artikel  >  Backend-Entwicklung  >  So verwenden Sie den längsten gemeinsamen Teilsequenzalgorithmus in C++

So verwenden Sie den längsten gemeinsamen Teilsequenzalgorithmus in C++

WBOY
WBOYOriginal
2023-09-19 15:54:35986Durchsuche

So verwenden Sie den längsten gemeinsamen Teilsequenzalgorithmus in C++

So verwenden Sie den Algorithmus für die längste gemeinsame Teilsequenz in C++

Die längste gemeinsame Teilsequenz (LCS) ist ein häufiges String-Matching-Problem, das verwendet wird, um die längste von zwei Zeichenfolgen derselben Teilsequenz zu finden. In C++ können wir dynamische Programmierung (Dynamic Programming) verwenden, um das LCS-Problem zu lösen.

Das Folgende ist ein C++-Codebeispiel, das zeigt, wie der Algorithmus für die längste gemeinsame Teilsequenz verwendet wird:

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

Im obigen Code verwenden wir zunächst dynamische Programmierung, um ein zweidimensionales Array zu erstellen. dp,其中dp[i][j]表示text1的前i个字符和text2的前j个字符所构成的最长公共子序列的长度。然后,我们根据动态规划的结果,利用dpDas Array erstellt die längste gemeinsame Teilsequenz. Zum Schluss geben Sie einfach die längste gemeinsame Teilsequenz aus.

Das Obige ist ein Beispiel für die Verwendung des längsten gemeinsamen Teilsequenzalgorithmus in C++. Durch die Idee der dynamischen Programmierung können wir das LCS-Problem effizient lösen und die längste gemeinsame Teilsequenz in zwei Zeichenfolgen finden.

Das obige ist der detaillierte Inhalt vonSo verwenden Sie den längsten gemeinsamen Teilsequenzalgorithmus in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Vorheriger Artikel:C-Programm für SechseckmusterNächster Artikel:C-Programm für Sechseckmuster