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

#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;
}