记录编号	241744	评测结果	AAAAA
题目名称	DNA螺旋串	最终得分	100
用户昵称	皮波Forever	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-03-26 08:46:17	内存使用	0.00 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 5010
#define max(a,b) (((a)>(b))?(a):(b))
using namespace std;
int MAIN();
void print(int,int);
short len1,len2,f[maxn][maxn],pre[maxn][maxn];
char s1[maxn],s2[maxn];
int haha=MAIN();
int main(){;}
inline int MAIN(){
#define COGS
#ifdef COGS
	freopen("lcsdna.in","r",stdin);
	freopen("lcsdna.out","w",stdout);
#endif
	scanf("%[A-Z]",s1);
	scanf("%*[^A-Z]");
	scanf("%[A-Z]",s2);
	len1=strlen(s1);
	len2=strlen(s2);
	for(int i=0;i<=len1;i++)f[i][0]=0;
	for(int j=0;j<=len2;j++)f[0][j]=0;
	for(int i=1;i<=len1;i++)for(int j=1;j<=len2;j++){
		if(s1[i-1]==s2[j-1])f[i][j]=f[i-1][j-1]+1,pre[i][j]=0;
		else if(f[i-1][j]<f[i][j-1])f[i][j]=f[i][j-1],pre[i][j]=2;
		else f[i][j]=f[i-1][j],pre[i][j]=1;
	}
	printf("%d\n",f[len1][len2]);
	print(len1,len2);
	return 0;
}
void print(int i,int j){
	label:
	if(!i||!j)return;
	if(!pre[i][j]){
		print(i-1,j-1);
		putchar(s1[i-1]);
	}
	else if(pre[i][j]==1){
		i--;
		goto label;
	}
	else{
		j--;
		goto label;
	}
}