SPOJ.COM - Thuật toán bài NKLETTER - Gửi thư

Đề bài:

Vị Giám đốc công ty XYZ cần gửi một văn bản quan trọng tới một đối tác của mình. Văn bản là một xâu S các chữ cái la tinh in thường. Để bảo mật nội dung văn bản, ông Giám đốc gửi 2 bức thư. Bức thư thứ nhất là phần đầu Sb của xâu S, bức thư thứ 2 là phần cuối Se của S. Hai bức thư Sb và Se đảm bảo đầy đủ nội dung của S, tuy nhiên có thể một phần cuối của Sb có thể được viết lặp lại trong phần đầu của Se, song số kí tự được viết lặp lại không biết trước.

Ví dụ: với văn bản S = 'truongnguyenduquannhat' tạo ra hai bức thư:

Sb = truongngueNdu

ngueNduquanNhat = Se

Sb = 'truongnguyendu' và Se = 'nguyenduquannhat'

Yêu cầu: Cho hai xâu Sb và Se, hãy xác định một xâu S có thể là nội dung của bức thư sao cho độ dài của xâu S là ngắn nhất.

Đầu vào

Dòng đầu chứa xâu Sb, dòng thứ hai chứa xâu Se. Mỗi xâu có độ dài không quá 250.

Đầu ra

Ghi ra độ dài của xâu S tìm được.

Ví dụ:

Đầu vào:

truongnguyendu 
nguyenduquannhat 

Đầu ra:

22 

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

Phân tích

Trong bài toán này mình sẽ sử dụng thuật toán tham lam - Greedy để giải quyết.

Tử tưởng chính là mình sẽ duyệt từ đầu đến cuối xâu SB. Với mỗi vị trí đó, mình sẽ so sánh thành phần từ vị trí đó đến cuối xâu của xâu SB với thành phần có độ dài tương ứng tính từ đầu mảng của SE.

Đến khi mình tìm được vị trí thỏa mãn đầu tiên, thì đó chính là thành phần trùng nhau của hai xâu thỏa mãn cho xâu S có độ dài nhỏ nhất.

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 = 505;
char SB[MAX], SE[MAX];  // Xâu đích S, xâu đầu SB và xâu cuối SE
int  LengB, LengE;      // Độ dài tương ứng của SB và SE.

/*
* Tính độ dài xâu
* @PARAM: str : xâu cần tính độ dài
* RETURN: độ dài xâu
*/
int GetLeng(char *str)
{
	int leng = 0;
	while(str[leng] != '\0') leng++;
	return leng;
}

/*
* Kiểm tra với với vị trí pos trên SB như vậy có thoả mãn hay không
* @PARAM: pos : vị trí đang xét trên SB.
* RETURN: true nếu hợp lệ, ngược lại là false
*/
bool IsValid(int pos)
{
	int leng1 = LengB - pos;
	if(leng1 > LengE) return false;

	for(int i = 0; i < leng1; i++)
		if(SB[pos + i] != SE[i]) return false;

	return true;
}

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

	// Nhập đầu vào
	cin >> SB >> SE;

	LengB = GetLeng(SB);
	LengE = GetLeng(SE);

	// Duyệt xâu SB từ đầu. Tại mỗi vị trí ta sẽ kiểm tra
	// thành phần cuổi của SB với thành phần đầu tương ứng của SE
	// - cùng độ dài. Nếu chúng giống nhau thì dừng lại.
	int pos = 0;
	for(pos = 0; pos < LengB; pos++)
		if(IsValid(pos)) break;

	int MinLen = pos + LengE;

	// In đầu ra
	cout << MinLen << endl;

	return 0;
}