当前位置: 首页 > article >正文

最长公共子序列【东北大学oj数据结构10-3】C++

题面

对于给定两个序列 X 和 Y , 序列 Z 是 X 和 Y 的公共子序列是指如果 Z 同时是 X 和 Y 的子序列。
例如:如果 X = {a, b, c, b, d, a, b} 和 Y = {b, d, c, a, b, a} ,
那么序列 {b, c, a} 是 X 和 Y 的一个公共子序列。
但是序列 { b , c, a } 不是 X 和 Y 的最长公共子序列(LCS) , 因为它的长度是3。
而序列 {b,c,b,a} ( X 和 Y 都有这个序列)的长度是 4, 又没有长度大于或等于 5 的公共子序列,所以序列 {b,c,b,a} 是 X 和 Y 的最长公共子序列。

编写一个程序,找出给定的两个序列 X 和 Y 的LCS的长度。

输入

输入由多个数据集组成。
在第一行中,给出了一个整数 q,它是数据集的数量。
在下面的 2 × q 行中,给出了由两个序列 X 和 Y 组成的每个数据集。

输出

对于每个数据集,在一行中打印 X 和 Y 的 LCS 长度。

约束

1≤q≤150
1≤X和Y的长度≤1000
如果数据集包含长度大于100的序列,则Q≤20

输入样例

3
abcbdab
bdcaba
abc
abc
abc
bc

输出样例

4
3

代码

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    for(int i=0;i<n;i++)
    {
        string a;
        string b;
        cin>>a>>b;
        int x=a.size();
        int y=b.size();
        vector<vector<int> > dq(x+1,vector<int>(y+1,0));
        for(int j=0;j<x;j++)
        {
            for(int k=0;k<y;k++)
            {
                if(a[j]==b[k])
                {
                    dq[j+1][k+1]=dq[j][k]+1;
                }
                else
                {
                    dq[j+1][k+1]=max(dq[j+1][k],dq[j][k+1]);
                }
            }
        }
        cout<<dq[x][y]<<endl;
    }
    return 0;
}


http://www.kler.cn/a/449335.html

相关文章:

  • 安宝特应用 | 美国OSHA扩展Vuzix AR眼镜应用,强化劳动安全与效率
  • Oracle Database 21c Express Edition数据库 和 Sqlplus客户端安装配置
  • D102【python 接口自动化学习】- pytest进阶之fixture用法
  • docker安装nginx,docker部署vue前端,以及docker部署java的jar部署
  • 深入理解 Linux wc 命令
  • 图解HTTP-HTTP报文
  • 我的PHP学习之路:经验分享与建议
  • leetcode-15.三数之和-day15(debug中...)
  • 【PythonGui实战】自动摇号小程序
  • 数据结构与算法学习笔记----质数
  • Rocky DEM tutorial6_High pressure grinding roll_高压辊磨机
  • DCDC Buck模式的电感值参数计算
  • 如何高效利用Python爬虫按关键字搜索苏宁商品
  • CSPM认证最推荐学习哪个级别?
  • 解决react 路由切换,页面闪屏的bug
  • 复习打卡大数据篇——Hadoop HDFS 02
  • 流年运势API接口_解析个人命理十年大运PHP实现方法返回json数据
  • virtualbox7 使用 自带的nat网络配置 解决虚机上网问题
  • Qt中的QProcess与Boost.Interprocess:实现多进程编程
  • Opencv之对图片的处理和运算
  • 【初阶数据结构与算法】八大排序算法之交换排序(冒泡排序,快速排序---hoare、挖坑法、lomuto双指针3种版本)
  • RCE 命令执行漏洞 过滤模式 基本的过滤问题 联合ctf题目进行实践
  • 【蓝桥杯——物联网设计与开发】拓展模块4 - 脉冲模块
  • CentOS7网络配置,解决不能联网、ping不通外网、主机的问题
  • 使用 Python 实现 WebSocket 服务器与客户端通信
  • 【Unity Shader】【图形渲染】Shader数学基础9 - 缩放矩阵