1953.cpp

来自「自己的ac代码 在acm.zju.edu.cn 上的题目」· C++ 代码 · 共 60 行

#include<stdio.h>
#include<string.h>
const int  MAXN=205;
char s[MAXN],t[MAXN];
int opt[MAXN][MAXN];
int main()
{
	int i,j,k;
	int n,m;
	while(scanf("%s%s",s,t)!=EOF)
	{
		n=strlen(s);
		m=strlen(t);
		for(i=0;i<MAXN;i++){opt[i][0]=0;opt[0][i]=0;}
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				if(s[i-1]==t[j-1])opt[i][j]=opt[i-1][j-1]+1;
				else
				{
					if(opt[i][j-1]>opt[i-1][j])opt[i][j]=opt[i][j-1];
					else opt[i][j]=opt[i-1][j];
				}

			}
		char temp[MAXN];int tc=0;
		while(n!=0 || m!=0)
		{
			if(s[n-1]==t[m-1])
			{
				temp[tc++]=s[n-1];
				n--;m--;
			}
			else if(opt[n][m-1]>=opt[n-1][m] && m>0)
			{
				temp[tc++]=t[m-1];
				m--;
			}
			else 
			{
				temp[tc++]=s[n-1];
				n--;
			}
		}
		for(i=tc-1;i>=0;i--)
			printf("%c",temp[i]);
		printf("\n");
	}
	return 0;
}