SPOJ.COM - Thuật toán bài ADFRUITS - Advanced Fruits

Posted on October 29th, 2016

Đề bài:

Công ty "21st Century Fruits" đã sáng tạo ra những loại nước hoa quả mới bằng cách chuyển gen từ một loại sang một loại khác. Hầu hết các lần là thất bại Nhưng đôi khi một loại nước hoa quả mới sẽ được tạo ra bằng cách trộn chúng lại với nhau.

Một chủ đề lớn được đưa ra thảo luận đó là "Phát minh mới này sẽ được gọi là gì?" Kết hợp giữa apple và pear sẽ được gọi là apple-pear. Dĩ nhiên, gọi như vậy nghe không hay ho lắm. Ông chủ công ty mới ra quyết định đó là sử dụng một chuỗi ngắn nhất chứa cả tên của cả hai loại. Ví dụ: "applear" bao gồm "apple" và "pear" (APPLEar và apPlEAR), và không có một xâu nào ngắn hơn thoả mãn tính chất trên.

Tổ hợp của "cranberry" và "boysenberry" là "boysecranberry" hay "craboysenberry" Nhiệm vụ của bạn là viết ra một chương trình để tính ra tên có độ dài nhỏ nhất là tổ hợp của 2 loại quả ban đầu.

Đầu vào

Mỗi dòng bao gồm 2 xâu là tên của 2 loại quả ban đầu. Tất cả tên có độ dài tối đa là 100 và chỉ chứa kí tự là chữ cái. Kết thúc đầu vào là kí hiệu kết thúc file.

Đầu ra

Mỗi test case, in ra tên nhỏ nhất của kết quả trên một dòng. Nếu có nhiều kết quả thì chỉ cần in ra một cái bất kỳ.

Ví dụ

Đầu vào:

apple peach
ananas banana
pear peach

Đầu ra:

appleach
bananas
pearch

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/ADFRUITS/

Phân tích

  • Ở đây mình sử dụng thuật toán quy hoạch động Dynamic programming để tìm ra dãy con chung dài nhất của hai cái tên.

  • Sau khi đã có dãy con chung dài nhất của của hai dãy rồi thì mình chỉ việc in ra kết quả theo thứ tự thỏa mãn bài toán.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/ C++

#include <iostream>
using namespace std;
const int MAX = 105;

char S1[MAX], S2[MAX];
int Leng1, Leng2;
int L[MAX][MAX];            // L[i][j] là độ dài LCS của S1[1..i] và S2[1...j]
char Common[MAX][MAX][MAX]; // Lưu thành phần chung dài nhất với L[i][j] trên.
char Result[2*MAX];         // Lưu kết quả
int Leng;                   // Độ dài mảng kết quả

/*
* Trả về độ dài xâu s
*/
int GetLeng(char *s)
{
	int leng = 0;
	while(s[leng] != '\0') leng++;
	return leng;
}

/*
* Sao chép xâu src với độ dài leng vào xâu dst
*/
void CpyStr(char *dst, char *src, int leng)
{
	for(int i = 0; i < leng; i++)
		dst[i] = src[i];
	dst[leng] = '\0';
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(false);
	//freopen("input.txt", "r", stdin);

	cin >> S1;
	while(true)
	{
		// Nhập xâu S1, S2 và tính độ dài của nó
		cin >> S2;
		Leng1 = GetLeng(S1);
		Leng2 = GetLeng(S2);

		// Trường hợp cơ sở 
		for(int i = 0; i <= Leng1; i++)
			L[i][0] = 0;
		for(int j = 0; j <= Leng2; j++)
			L[0][j] = 0;

		for(int i = 1; i <= Leng1; i++)
			for(int j = 1; j <= Leng2; j++)
			{
				// Chỉ số mảng char* tính từ 0
				// Nếu hai kí tự đang xét giống nhau
				// thì cho vào dãy chung tăng dài nhất
				if(S1[i-1] == S2[j-1])
				{
					L[i][j] = 1 + L[i-1][j-1];
					CpyStr(Common[i][j], Common[i-1][j-1], L[i-1][j-1]);

					Common[i][j][L[i][j] - 1] = S1[i - 1];
					Common[i][j][L[i][j]] = '\0';
				}
				else // S1[i-1] != S2[j-1] thì giữ lại dãy nào có độ dài lớn hơn
				{
					// Chọn thành phần lớn hơn
					if(L[i-1][j] > L[i][j-1])
					{
						L[i][j] = L[i-1][j];
						CpyStr(Common[i][j], Common[i-1][j], L[i-1][j]);
					}
					else
					{
						L[i][j] = L[i][j-1];
						CpyStr(Common[i][j], Common[i][j-1], L[i][j-1]);
					}
				}
			}

        // In kết quả
		int i1 = 0;	// Con trỏ vào đầu s1
		int i2 = 0; // Con trỏ vào đầu s2
		int c  = 0; // Con trỏ vào đầu xâu common[Leng1][Leng2]
		
		Leng = 0;
		while(Common[Leng1][Leng2][c] != '\0')
		{
		    // In ra thành phần ở S1 cho đến thành phần chung
			while(S1[i1] != Common[Leng1][Leng2][c]) 
				Result[Leng++] = S1[i1++];

            // In ra thành phần sở S2 cho đến thành phần chung
			while (S2[i2] != Common[Leng1][Leng2][c])
				Result[Leng++] = S2[i2++];

            // In ra thành phần chung, rồi tăng con trỏ lên và tiếp tục
			Result[Leng++] = Common[Leng1][Leng2][c];
			c  += 1;
			i1 += 1;
			i2 += 1;
		}

        // Sau khi in hết thành phần chung rồi, thì in nốt S1 rồi S2
		for(int i = i1; i < Leng1; i++)
			Result[Leng++] = S1[i];
		for(int i = i2; i < Leng2; i++)
			Result[Leng++] = S2[i];
		Result[Leng] = '\0';

		cout << Result << endl;
		if(!(cin >> S1)) break;
	}
	return 0;
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé:

Xin chào và hẹn gặp lại, thân ái!