Heim > Artikel > Backend-Entwicklung > 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
个字符所构成的最长公共子序列的长度。然后,我们根据动态规划的结果,利用dp
Das 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!