神农架野人问题（输出序列）

Question

Description
最近网上热炒神农架野人考察话题，有支持有反对的，据说曾经有人捡到过不少野人头发，那么到底捡到的头发是不是野人的呢？不是最新科技有DNA检测方法吗？由于没有已经抓到的或者现成的野人，哪里去找比对需要的野人的DNA呢？所以只能另辟蹊径了，假如在被捡到的头发里能够提取最多26个特征，这些特征用英文大写字母表示，一根头发有一系列特征序列组成，科学家又通过科学方法分析出了很多可能的野人的头发的参考特征序列，如果两种特征序列（捡到的头发的特征序列和参考的特征序列）的公共子序列越长表示越接近，现在请你帮助计算出最长的公共特征。

Input
本问题有多组测试数据，第一行就是测试数据的组数（1<=组数<=20）。对于每一组测试数据，有两行，每一行都是有大写英文字母组成的特征序列（1<=特征序列的长度<=1000）。

Output
对于每一组输入，对应的输出有两行，第一行是最长的公共子序列的长度，第二行是最长的公共特征串，当有不止一个串符合条件时，按照公共串在第一个原串的位置优先（如果第一个元素位置相同，就比较第二个元素，依次类推）为条件，输出最先的子串。

Sample Input
1
ABDCRHGWDWSDSKJDSKDFHJKFDKJDSAFKJFDAKFDSAJFDKASDJLFLDKF
ERUDSHDFHGFLKGFGFKGFLKSAEWALUTRHGFKIFDGITRMDFLKDSLSDLLEHJFKLEKIREFMFK
Sample Output
25
RDSDKFKFKSAFKFDKDSSDJFLKF

Answer 1

#include<bits/stdc++.h>
using namespace std;
int dp[1001][1001]; 
int main()
{
    int t,i,j,k,ax,ay;
    string sx,sy;
    cin>>t;
    for(k=1;k<=t;k++)
    {
        cin>>sx>>sy;
        sx='0'+sx;
        memset(dp,0,sizeof(dp));
        sy='0'+sy;
        ax=sx.size();
        ay=sy.size();
        for(i=1;i<ax;i++)
        {
            for(j=1;j<=ay;j++)
            {
                if(sx[i]==sy[j])
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else
                {
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        cout<<dp[i-1][j-1]<<endl;
    }
    return 0;
}