Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
题目描述
给定两个字符串str1和str2，输出连个字符串的最长公共子序列。如过最长公共子序列为空，则输出-1。
输入描述:
输出包括两行，第一行代表字符串str1，第二行代表str2。( 1<= length(str1),length(str2)<= 5000)
输出描述:
输出一行，代表他们最长公共子序列。如果公共子序列的长度为空，则输出-1。
示例1
输入
1A2C3D4B56
B1D23CA45B6A
输出
123456
说明
“123456”和“12C4B6”都是最长公共子序列，任意输出一个。
备注:
时间复杂度O(nm)O(n∗m)，空间复杂度O(nm)O(n∗m)。(n,m分别表示两个字符串长度)
#include<bits/stdc++.h>
#define x first
#define y second
#define send string::nops
using namespace std;
typedef long long ll;
const int N = 1e4 + 10;
const int M = 3 * N;
const int INF = 0x3f3f3f3f;
typedef pair<int,int> PII;
int f[N][N],path[N][N];//path用来记录dp路径
int main(){
string str1,str2;
cin>>str1>>str2;
int n = str1.size(),m = str2.size();
str1.insert(0,1,' ');
str2.insert(0,1,' ');
// cout<<str1<<endl;
for(int i = 1;i < str1.size();i ++){
for(int j = 1;j < str2.size();j ++){
if(str1[i] == str2[j])f[i][j] = f[i - 1][j - 1] + 1,path[i][j] = m * (i - 1) + j - 1;
else {
f[i][j] = max(f[i - 1][j],f[i][j - 1]);
if(f[i - 1][j] > f[i][j - 1])path[i][j] = m * (i - 1) + j;
else path[i][j] = m * i + j - 1;
}
}
}
int a = str1.size() - 1,b = str2.size() - 1;
vector<char>res;
while(a > 0 && b > 0){
// cout<<a <<"--"<<b<<endl;
// cout<<f[a][b]<<endl;
// cout<<f[a - 1][b - 1]<<endl;
// cout<<f[a - 1][b]<<endl;
// cout<<f[a][b - 1]<<endl;
int tt = path[a][b];
int x = tt / m,y = tt % m;
// cout<<x<<"--"<<y<<endl;
if(x == a - 1 && y == b - 1 && !(x == 0 && y == 0))res.push_back(str1[a]);
a = x,b = y;
}
reverse(res.begin(),res.end());
if(res.size() == 0){
cout<<-1<<endl;
return 0;
}
for(int i = 0;i < res.size();i ++)cout<<res[i];
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/168791.html原文链接：https://javaforall.net
