2080 最长公共子序列问题

谁践踏了优雅 2022-02-16 08:18 88阅读 0赞

### 最长公共子序列问题 ###

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定两个序列 X=\{x1,x2,…,xm\} 和 Y=\{y1,y2,…,yn\}，找出X和Y的最长公共子序列。

Input

输入数据有多组，每组有两行 ，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,Z）），表示序列X和Y。

Output

每组输出一行，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出0。

Sample Input

ABCBDAB
    BDCABA

Sample Output

4

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<malloc.h>
    int max(int x,int y){return x>y?x:y;}
    int main()
    {
        char s1[1000],s2[1000],a[600][600];
        while (~scanf("%s", s1)) {
          scanf("%s", s2);
          len1 = strlen(s1);
          len2 = strlen(s2);
          for(i = 0; i <= len1; i++)
            a[i][0] = 0;
          for(i = 0; i <= len2; i++)
            a[0][i] = 0;
          for(i = 1; i <= len1; i++)
            for(j = 1; j <= len2; j++){
              if(s1[i-1]==s2[j-1])
                a[i][j] = a[i-1][j-1] +1;    //a[i][j] 表示s1[i]和s2[j]的最大公共子序列数
                int len1,len2,i,j;
              else
                a[i][j] = max(a[i-1][j],a[i][j-1]);
            }
          printf("%d\n",a[len1][len2]);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，88人围观）

还没有评论，来说两句吧...

相关阅读

相关最长公共子序列空间优化最长公共子序列

import java.util.Scanner; / HDU 1159 @author ashzheng 201

ゞ浴缸里的玫瑰/ 2022年08月21日 05:46/ 0 赞/ 286 阅读

相关最长公共子序列问题

Problem Description 给定两个序列X= Input 输入数据有多组，每组有两行，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,

太过爱你忘了你带给我的痛/ 2022年07月12日 03:16/ 0 赞/ 151 阅读

相关最长公共子序列问题

Problem Description 给定两个序列X= Input 输入数据有多组，每组有两行，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,

蔚落/ 2022年07月12日 03:16/ 0 赞/ 153 阅读

相关最长公共子序列问题2080

集训的时候老师讲的时候就不是很懂，几天没做，更是忘得一干二净了，从网上找了一份大神的笔记，顿时清晰了好多。 [点击打开链接][Link 1] 动态规划法（看大神的笔记

r囧r小猫/ 2022年06月09日 01:44/ 0 赞/ 84 阅读

相关最长公共子序列问题

Problem Description 给定两个序列 X=\{x1,x2,…,xm\} 和 Y=\{y1,y2,…,yn\}，找出X和Y的最长公共子序列。 Input

你的名字/ 2022年05月16日 01:40/ 0 赞/ 167 阅读

相关最长公共子序列问题

最长公共子序列问题 Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [Statistic][] Prob

向右看齐/ 2022年02月25日 07:07/ 0 赞/ 194 阅读

相关最长公共子序列问题

最长公共子序列问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 给定两个序列 X=

我就是我/ 2022年02月17日 12:17/ 0 赞/ 190 阅读

相关 2080 最长公共子序列问题

最长公共子序列问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 给定两个序列 X=

谁践踏了优雅/ 2022年02月16日 08:18/ 0 赞/ 89 阅读

相关最长公共子序列问题

[参考：https://blog.csdn.net/huanghanqian/article/details/78892808][https_blog.csdn.net_hu

川长思鸟来/ 2022年02月16日 02:30/ 0 赞/ 201 阅读

相关最长公共子序列

最长公共子序列设X=<x1,x2,x3,x4…,xm>，Y=<y1,y2,y3,y4…,yn>为两个序列，Z=<z1,z2,z3,z4…,zk>是他们的任意公共子序列

迈不过友情╰/ 2021年10月19日 05:48/ 0 赞/ 383 阅读