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

Question

我有一个“最长公共(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

Answer 1

一种粗略的做法是在 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)子序列长度。您可以轻松地为此进行必要的更改。