SDUT 2080 最长公共子序列问题

seven_ • 2023年2月21日下午10:13 • Python • 阅读 306

最长公共子序列

题目

Problem Description
给定两个序列X=
Input
输入数据有多组，每组有两行，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,Z）），表示序列X和Y。
Output
每组输出一行，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出0。
Sample Input
ABCBDAB
BDCABA
Sample Output
4

代码&分析

这算是动态规划最经典的一道题目了，还有矩阵链乘法。

#include<stdio.h>
#include<memory.h>
#include<iostream>
using namespace std;
int s[502][502];
string s1, s2;
/*
  关键在于对于两个序列的某一点s1[i]与s2[j]，
  如果两者相等，那么到i,j为止，最长子序列等于s1(0~i-1) 与 s2(0~j-1) 的最长子序列（LCS） + 1；
  如果两者不相等，那么到i,j为止，最长子序列等于 LCS(s1(0~i-1),s2(0,j))或者LCS(s1(0~i),s2(0~j-1))
  至于取哪一个，自然是取之中较大的那一个了
*/

int main(){
    while(cin>>s1){
        cin>>s2;
        int l1 = s1.length();
        int l2 = s2.length();
        s1 = ' ' + s1;
        s2 = ' ' + s2;      //这样只是为了让s1[1]就是s1的第一个字符，表示比较清楚，也可以不使用这种方式
        memset(s, 0, sizeof(s));
        for(int i=0; i<=l1; i++)
            s[i][0] = 0;
        for(int i=0; i<=l2; i++)
            s[0][i] = 0;
        for(int i=1; i<=l1; i++){
            for(int j=1; j<=l2; j++){
                if(s1[i]==s2[j])
                    s[i][j] = s[i-1][j-1] + 1;
                else
                    s[i][j] = max(s[i-1][j], s[i][j-1]);
            }
        }
        /*for(int i=0;i<=l1;i++){
            for(int j=0; j<=l2; j++)
                cout<<s[i][j]<<" ";
            cout<<endl;
        }*/                             //这个矩阵就是整个的过程
        cout<<s[l1][l2]<<endl;
    }
}