gpt4 book ai didi

c++ - 如何使用递归打印最长公共(public)子序列中涉及的字符串?

转载 作者:行者123 更新时间:2023-11-28 04:03:08 25 4
gpt4 key购买 nike

我有一个“最长公共(public)子序列”的代码,但我不仅想要最长的长度,而且还想要 其中涉及的字符串 使用递归。

我们将不胜感激。

下面的代码只会给出最长的长度

#include<iostream>
#include<string>

using namespace std;

int longest_seq( string s1, string s2, int n1, int n2)
{
if( n1 < 0 || n2 < 0)
return 0;

// If last char of both the string matches
if( s1[n1] == s2[n2])
return ( 1 + longest_seq(s1, s2, n1-1, n2-1));

else
return max(longest_seq(s1, s2, n1-1, n2),longest_seq(s1, s2, n1, n2-1));
}

int main()
{
string s1 = "AGGTAB";
string s2 = "GXTXAYB";

int n1 = s1.length();
int n2 = s2.length();

cout <<longest_seq(s1, s2, n1-1, n2-1);

return 0;
}

当前输出:

4

预期输出:

4     
GTAB

最佳答案

一种粗略的做法是在 longest_seq() 函数中传递一个空字符串,该函数将使用公共(public)子序列填充该字符串。

基本上你是这样做的-

int main()
{
string s1 = "AGGTAB";
string s2 = "GXTXAYB";
string out;

int n1 = s1.length();
int n2 = s2.length();

// Pass out as an input param
cout <<longest_seq(s1, s2, n1-1, n2-1, out) << endl;
cout << out << endl;

return 0;
}

您也需要更改 longest_seq()

int longest_seq( string s1, string s2, int n1, int n2, string& out)
{
if( n1 < 0 || n2 < 0)
return 0;

// If last char of both the string matches
if( s1[n1] == s2[n2]) {
out.insert(0, 1, s1[n1]); // Push the matching character in front
return ( 1 + longest_seq(s1, s2, n1-1, n2-1, out));
} else {
string out1, out2; // temporary strings
int len1 = longest_seq(s1, s2, n1-1, n2, out1);
int len2 = longest_seq(s1, s2, n1, n2-1, out2);
out.insert(0, len1>len2 ? out1 : out2); // Add the correct one to the front
return max(len1, len2);
}
}

输出:

4
GTAB

您还可以更改函数以返回字符串,而不是将输出字符串作为参数传递。然后在函数返回后,您可以轻松检查函数输出的长度以获得最长的公共(public)子序列长度。您可以轻松地为此进行必要的更改。

关于c++ - 如何使用递归打印最长公共(public)子序列中涉及的字符串?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59170003/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com