首页 > 其他 > 详细

最长公共子序列板/滚动

时间:2017-09-30 14:06:35      阅读:216      评论:0      收藏:0      [点我收藏+]

技术分享

 

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int i,j,dp[2][10086],t;
    char a[10086],b[10086];
    bool now,pre;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%s",a,b);
        memset(dp,0,sizeof(dp));
        int lena=strlen(a),lenb=strlen(b);
        for(now=1,pre=0,i=0; i<lena; i++)
            for(swap(now,pre),j=0; j<lenb; j++)
                if(a[i]==b[j])
                    dp[now][j+1]=dp[pre][j]+1;
                else
                    dp[now][j+1]=dp[pre][j+1]>dp[now][j]?dp[pre][j+1]:dp[now][j];
        printf("%d\n",dp[now][lenb]);
    }
    return 0;
}

 

最长公共子序列板/滚动

原文:http://www.cnblogs.com/Aragaki/p/7614602.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!