pku2264.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>

char sa[101], sb[101];
int DP[101][101];
int la, lb, lab;

int ka[101], kb[101];

int max(int x, int y)
{
	return (x > y) ? x : y;
}

int Test(int i, int j)
{
	int k = 0;
	while (i < la && j < lb)
	{
		k++;
		if (DP[i][j] + 1 == DP[i + 1][j + 1])
		{
			return k;
		}
		i++;
		j++;
	}
	return 0;
}

int main()
{
	int i, j, tes, ia, ib;
	while (scanf("%s %s", &sa, &sb) != -1)
	{
		la = strlen(sa);
		lb = strlen(sb);
		memset(DP, 0, sizeof(DP));
		for (i = 1; i <= la; i++)
		{
			for (j = 1; j <= lb; j++)
			{
				if (sa[i - 1] == sb[j - 1])
				{
					DP[i][j] = DP[i - 1][j - 1] + 1;
				}
				else
				{
					DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
				}
			}
		}
		lab = DP[la][lb];
		for (i = lab, ia = la, ib = lb; i > 0; i--)
		{
			while (DP[ia][ib] == DP[ia - 1][ib]) ia--;
			while (DP[ia][ib] == DP[ia][ib - 1]) ib--;
			ka[i - 1] = ia - 1;
			kb[i - 1] = ib - 1;
			ib--;
			ia--;
		}
		for (i = 0, ia = 0, ib = 0; i < lab;i++)
		{
			while (ia < ka[i])
				putchar(sa[ia++]);
			while (ib < kb[i])
				putchar(sb[ib++]);
			putchar(sa[ia]);
			ia++;
			ib++;
		}
		while (ia < la)
			putchar(sa[ia++]);
		while (ib < lb)
			putchar(sb[ib++]);
		printf("\n");
	}
	return 0;
}