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

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

输入

第1行: 两个数: N1,N2 第2行:N1个字符 第3行:N2个字符

输出

2 2 CT AG

样例

输入

0

输出


                
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题