Giả sử ta có hai chuỗi text1 và text2, ta phải trả về độ dài của dãy con chung dài nhất của chúng. Dãy con của một chuỗi là chuỗi mới sinh ra từ chuỗi gốc bằng cách xóa một số ký tự mà không thay đổi thứ tự tương đối của các ký tự còn lại. (Ví dụ "abe" là dãy con của "abcde" nhưng "adc" không phải). Dãy con chung của hai chuỗi là dãy con chung cho cả hai. Nếu không có dãy con chung, trả về 0. Ví dụ: "abcde" và "ace" cho kết quả 3.
Để giải quyết, ta thực hiện các bước sau:
n := kích thước s, m := kích thước x.
Nếu n bằng 0 hoặc m bằng 0, trả về 0.
s := chuỗi rỗng nối với s.
x := chuỗi rỗng nối với x.
ret := 0.
Định nghĩa ma trận dp kích thước (n + 1) x (m + 1).
Với i từ 1 đến n:
Với j từ 1 đến m:
dp[i, j] := max của dp[i, j - 1] và dp[i - 1, j].
Nếu s[i] = x[j], thì:
dp[i, j] := max của dp[i, j] và 1 + dp[i - 1, j - 1].
Trả về dp[n, m].
Xem triển khai dưới đây để hiểu rõ hơn:
Ví dụ minh họa
#include <bits/stdc++.h> using namespace std; class Solution { public: int longestCommonSubsequence(string s, string x) { int n = s.size(); int m = x.size(); if(!n || !m) return 0; s = " " + s; x = " " + x; int ret = 0; vector < vector <int> > dp(n + 1, vector <int>(m + 1)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= m ; j++){ dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); if(s[i] == x[j]) { dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]); } } } return dp[n][m]; } }; main(){ Solution ob; cout << (ob.longestCommonSubsequence("abcde", "ace")); }Đầu vào
"abcde" "ace"
Kết quả
3