Algorithm yyds 2022-03-16 16:55 采纳率: 100%
浏览 48
已结题

神农架野人问题(输出序列)

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

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

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

Sample Input
1
ABDCRHGWDWSDSKJDSKDFHJKFDKJDSAFKJFDAKFDSAJFDKASDJLFLDKF
ERUDSHDFHGFLKGFGFKGFLKSAEWALUTRHGFKIFDGITRMDFLKDSLSDLLEHJFKLEKIREFMFK
Sample Output
25
RDSDKFKFKSAFKFDKDSSDJFLKF

  • 写回答

1条回答 默认 最新

  • 卡尔曼的BD SLAMer 计算机视觉领域新星创作者 2022-03-16 17:25
    关注
    
    #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;
    }
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 3月24日
  • 已采纳回答 3月16日
  • 创建了问题 3月16日

悬赏问题

  • ¥15 电信IPV6 无法外网访问吗
  • ¥15 有偿求效果比较好的遥感影像匹配的c++代码
  • ¥15 博主,你好,我下载了你的智能网联汽车辅助驾驶安全信息检测系统,现在不会运行,可以教我吗,
  • ¥15 怎么在excle输入下列公式
  • ¥15 Arduino,利用modbus的RS485协议,进行对外置的温湿度传感器进行数据读取
  • ¥15 vhdl+MODELSIM
  • ¥20 simulink中怎么使用solve函数?
  • ¥30 dspbuilder中使用signalcompiler时报错Error during compilation: Fitter failed,求解决办法
  • ¥15 gwas 分析-数据质控之过滤稀有突变中出现的问题
  • ¥15 没有注册类 (异常来自 HRESULT: 0x80040154 (REGDB_E_CLASSNOTREG))