基于位运算的最长公共子序列

时间限制:30s      空间限制:128MB

题目描述

小欣在公园玩时发现有个玩小游戏的地方,小游戏的规则是:有两排标有字符的球,字符属于{ATCG},第1排有N1个球,第2排有N2个球(1<=N1,N2<=50000),在第1排的球中选出1些来和第2排的配对,每配出1对就得1分,已经配对了的就不能再用了。小欣觉得这个游戏太简单了,不就是用个就可以了吗?但他发现规则的最后1行说:配对的连线不能相交,相交的概念就是对于第1排的IJ2个球,它们配对的分别是F[I]F[J],它们相交当且仅当I<J and F[I]>F[J]。这就难倒小欣了,现在请你帮助小欣编程求出最大得分。


输入格式

1两个数: N1N2

2行:N1个字符

3行:N2个字符


输出格式

2 2

CT

AG


样例输入

0

样例输出


提示

没有写明提示


题目来源

没有写明来源

Menuappsclose