洛谷-最长公共子串「建议收藏」

编程汇总 • 2025-07-03 08:01 • 阅读 90

题目描述
给定两个字符串str1和str2，输出连个字符串的最长公共子序列。如过最长公共子序列为空，则输出-1。
输入描述:
输出包括两行，第一行代表字符串str1，第二行代表str2。( 1<= length(str1),length(str2)<= 5000)
输出描述:
输出一行，代表他们最长公共子序列。如果公共子序列的长度为空，则输出-1。
示例1
输入

1A2C3D4B56

B1D23CA45B6A

输出

说明
“123456”和“12C4B6”都是最长公共子序列，任意输出一个。
备注:

时间复杂度O(nm)O(n∗m)，空间复杂度O(nm)O(n∗m)。(n,m分别表示两个字符串长度)

#include

#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 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<
    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;

    vectorres;

    while(a > 0 && b > 0){ 

   

// cout<
// cout<
// cout<
// cout<
// cout<
        int tt = path[a][b];

        int x = tt / m,y = tt % m;

// cout<
        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<
        return 0;

    }

    for(int i = 0;i < res.size();i ++)cout<
    return 0;

}

洛谷-最长公共子串「建议收藏」

相关推荐