Một dãy con là một dãy có cùng thứ tự của tập hợp các phần tử. Đối với chuỗi “stuv”, các chuỗi con là “stu”, “tuv”, “suv”, .... v.v.
Đối với một chuỗi có độ dài n, có thể có 2n cách để tạo dãy con từ chuỗi.
Ví dụ
Chuỗi con chung dài nhất cho các chuỗi “ABCDGH” và “AEDFHR” có độ dài là 3.
#include <iostream>
#include <string.h>
using namespace std;
int max(int a, int b);
int lcs(char* X, char* Y, int m, int n){
if (m == 0 || n == 0)
return 0;
if (X[m - 1] == Y[n - 1])
return 1 + lcs(X, Y, m - 1, n - 1);
else
return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
}
int max(int a, int b){
return (a > b) ? a : b;
}
int main(){
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
int m = strlen(X);
int n = strlen(Y);
printf("Length of LCS is %d\n", lcs(X, Y, m, n));
return 0;
} Đầu ra
Length of LCS is 4