最长公共子序列问题

我就是我 2022-02-17 12:17 179阅读 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 <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        char s1[510], s2[510];
        int l1, l2;
        int i, j;
        int s[510][510];
        while(~scanf("%s%s", s1, s2))
        {
            l1 = strlen(s1);
            l2 = strlen(s2);
            for(i = 0; i <= l1; i++)
            {
                s[i][0] = 0;
            }
            for(i = 0; i <= l2; i++)
            {
                s[0][i] = 0;
            }
            for(i = 1; i <= l1; i++)
            {
                for(j = 1; j <= l2; j++)
                {
                    if(s1[i - 1] == s2[j - 1])
                    {
                        s[i][j] = s[i - 1][j - 1] + 1;
                    }
                    else
                    {
                        s[i][j] = max(s[i - 1][j], s[i][j - 1]);
                    }
                }
            }
            printf("%d\n", s[l1][l2]);
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关最长公共子序列问题

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

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

相关最长公共子序列问题

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

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

相关最长公共子序列问题

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

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

相关最长公共子序列

最长公共子序列问题，具有最优子结构性质设序列Xm=\{x1,x2,…,xm\}和Yn=\{y1,y2,…,yn\}的最长公共子序列为Zk=\{z1

港控/mmm°/ 2022年04月23日 07:04/ 0 赞/ 258 阅读

相关最长公共子序列问题

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

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

相关最长公共子序列问题

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

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

相关最长公共子序列问题

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

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

相关最长公共子序列

找出两个字符串的最长公共子序列。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLm

r囧r小猫/ 2021年11月09日 17:10/ 0 赞/ 394 阅读

相关最长公共子序列

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

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