SDUT 2080 最长公共子序列问题

xiaoxiao2021-02-28  18

最长公共子序列

题目

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; } }
转载请注明原文地址: https://www.6miu.com/read-2599972.html

最新回复(0)