Bài toán xâu con chung dài nhất C/C++| Longest common subsequence

Bài viết chia sẻ cách giải quyết bài toán xâu con chung dài nhất (LCS – Longest common subsequence) bằng ngôn ngữ C/C++. Độ dài xâu con chung lớn nhất sử dụng thuật toán quy hoạch động. Cách truy vết, in ra dãy con tăng liên tiếp theo. . .

1. Giới thiệu bài toán LCS

Bài toán xâu con chung dài nhất (lớn nhất) là một bài toán kinh điển cho việc ứng dụng thuật toán quy hoạch động để giải quyết. Bạn là người đang tìm hiểu về Dynamic Programming, đừng bỏ lỡ bài toán này. Có thể nói, đây là một bài toán rất hay giúp bạn hiểu cả về QHD, cả về cấu trúc ma trận mảng hai chiều.

Bài toán được phát biểu như sau:

Viết chương trình nhập vào hai xâu kí tự, in ra độ dài xâu con chung lớn nhất và xâu chung đó của hai xâu vừa nhập.
Ví dụ:  hai xâu “BACDB” và “BDCB”, xâu con chung lớn nhất có độ dài là 3 và là “BCB”.

Như vậy có hai điểm cần chú ý trong bài toán này đó là:

• Tìm độ dài của xâu con chung dài nhất
• In xâu con tìm được ra màn hình

2. Ý tưởng giải quyết bài toán

Như đã nói ở phần đầu, bài toán này mình sẽ sử dụng thuật toán quy hoạch động. Nếu bạn chưa hiểu rõ về thuật toán QHD, có thể tham khảo thêm tại đây. Ngoài ra để lưu lời giải của các bài toán con sử dụng đến cấu trúc mảng hai chiều C/C++, chính vì thế hãy làm chủ nó trước nhé!

2.1 Tìm độ dài xâu con lớn nhất

Bài toán nhỏ nhất ở đây chính là việc so sánh các phần tử nằm trong xâu, nếu chúng bằng nhau thì ta ghi nhật kết quả.

Công thức quy hoạch động bài toán xâu con chung lớn nhất:

• Nếu A[i] == B[j] thì L[i][j] = L[i-1][j-1] + 1
• Ngược lại thì L[i][j] = max (L[i-1][j], L[i][j-1])

Trong đó:

• A, B là hai xâu cần xét
• i, j tương ứng là chỉ số hàng và cột của mảng kết quả L
• Hàm max là hàm để tìm ra số lớn hơn trong hai số, trường hợp hai số bằng nhau thì lấy số đầu tiên – L[i-1][j-1]

Để dễ hiểu hơn bạn xem hình minh họa dưới đây:

Mảng lưu kết quả là một mảng hai chiều có kích thước L[n+1][m+1] trong đó n, m chính là độ dài của hai xâu a và b.
Sở dĩ phải tăng thêm một đơn vị (n+1, m+1) để lưu thêm một hàng, cột có giá trị = 0. Tức là khi chưa có phần tử nào thì số con chung sẽ là 0.

Giá trị L[n][m] chính là độ dài của xâu con chung lớn nhất ta cần tìm.

2.2 Truy vết xâu con chung

Truy vết để tìm và in ra xâu con ra màn hình sẽ dựa vào bảng kết quả mà ta tìm được ở phần trên. Bắt đầu từ vị trí L[n][m] và dừng lại khi L[i][j] == 0.

• Bắt đầu duyệt từ i = n , j = m. Phần tử thứ i của xâu a sẽ là a[i-1], thứ j của xâu b sẽ là b[j-1]
• Nếu a[i-1] == b[j-1] ta sẽ lưu lại con chung a[i-1] và giảm i và j đi 1 đơn vị
• Nếu a[i-1] != b[j-1] có 2 trường hợp:
  – Nếu L[i-1][j] >= L[i][j-1] thì giảm i 1 đơn vị
  – Ngược lại giảm j đi 1 đơn vị

Nếu thấy khó hiểu, bạn xem hình phía trên. Màu green là trường hợp a[i-1] == b[j-1], màu blue là trường hợp a[i-1] != b[j-1]

3. Code xâu con chung dài nhất C/C++

Phần này mình sẽ trình bày code theo đúng ý tưởng đã nếu ở phần trên. Mời bạn tham khảo

/* COde by https://duongdinh24.com/ 
   Github: https://github.com/duongdinh24/
*/
#include<iostream>
#include<string>  // Thư viện xử lý xâu
using namespace std;

void longest_Common(string a, string b){  // Hàm tìm xâu con lớn nhất và in ra màn hình
	int n = a.size();  // n chiều dài xâu a, m chiều dài xâu b
	int m = b.size();
	int max_Size;     // Biến lưu độ dài con chung lớn nhất
	string subsequence = "";  // Biến lưu con chung dùng khi truy vết
	int L[n+1][m+1];   // Khai báo mảng lưu kết quả:  n+1 hàng, m+1 cột
	
	for(int i=0; i<=n; i++)   // Gán cột đầu tiên bằng 0
		L[i][0] = 0;
	for(int j=0; j<=m; j++)   // Gán hàng đầu tiên = 0
		L[0][j] = 0;
		
	for(int i = 1; i<=n; i++){
		for(int j = 1; j<=m; j++){
			if(a[i-1] == b[j-1]){  // Nếu có phần tử bằng nhau
				L[i][j] = L[i-1][j-1] + 1;   // Áp dụng công thức
			}
			else{   // Trường hợp a[i-1] khác b[j-1]
				if(L[i-1][j] >= L[i][j-1])     // Tìm max giữa L[i-1][j] và L[i][j-1]
					L[i][j] = L[i-1][j];
				else
					L[i][j] = L[i][j-1];
			}
		}
	}
	
	max_Size = L[n][m];  // Tìm được độ dài con lớn nhất
	int i = n; 
	int j = m;
	while(L[i][j] != 0){ // Điều kiện dừng
		if(a[i-1] == b[j-1]){  // Nếu bằng nhau
			subsequence += a[i-1];   // Cộng a[i-1] vào xâu con
			i--;
			j--;
		}
		else{  // Nếu khác nhau
			if(L[i-1][j] >= L[i][j-1]) // So sánh
				i--;
			else
				j--;
		}
	}
	
	cout<<"\nDo dai xau lon nhat: "<<max_Size;  // In ra độ dài con lớn nhất
	cout<<"\nXau con: ";
	for(int t = max_Size-1 ; t>=0; t--)  // In ngược từ cuối về đầu để xâu con đúng thứ tự
		cout<<subsequence[t];
}
int main(){
	string a, b;
	cout<<"Nhap xau a: "; cin>>a;
	cout<<"Nhap xau b: "; cin>>b;
	longest_Common(a,b);
	return 0;	
}

Và đây là kết quả chạy chương trình trên:

Bài viết của mình đến đây là hết, nếu bạn có bất kì thắc mắc nào, đừng ngại để lại comment xuống phía dưới nhé! Cảm ơn bạn đã quan tâm bài viết này.

Xem thêm các bài viết về ứng dụng thuật toán khác tại đây.