动态规划求最长公共子序列，存在多个解时只能输出一个。

//求取所有的最长公共子序列
不知道代码哪里写错了，也只有一个币能悬赏，希望有空的大神们帮忙看看，纠结好久了不知道怎么改。
#include
using namespace std;

const int X=100, Y= 100; //串的最大长度
char result[X+1]; //用于保存结果
int count= 0; //用于保存公共最长公共子串的个数

/*功能：计算最优值
*参数：

• x:字符串x
• y:字符串y
• b:标志数组
• xlen:字符串x的长度

•    ylen:字符串y的长度
  

  返回值：最长公共子序列的长度
  *
  */
  int Lcs_Length(string x, string y, int b[][Y+1],int xlen,int ylen)
  {
  int i= 0;
  int j= 0;
  int c[X+1][Y+1];
  /

  • 下面两个for循环将第一行和第一列全置为0
    */
    for (i = 0; i<=xlen; i++)
    {
    c[i][0]=0;
    }

    for (i = 0; i <= ylen; i++ )
    {
    c[0][i]=0;
    }

  for (i = 1; i <= xlen; i++)
  {
  
  for (j = 1; j <= ylen; j++)
  {
  if ( x[i-1] == y[j-1] )
  {
  c[i][j] = c[i-1][j-1]+1;
  b[i][j] = 1;
  }
  else // c[i][j] = max( c[i-1][j] , c[i][j-1] )
  {
  if ( c[i-1][j] > c[i][j-1] )
  {
  c[i][j] = c[i-1][j]; // 向上
  b[i][j] = 2;
  }
  else
  {
  if( c[i-1][j] < c[i][j-1] )
  {
  c[i][j] = c[i][j-1]; // 向左
  b[i][j] = 3;
  }
  }
  }
  }
  }
  cout << "计算最优值效果图如下所示：" << endl;
  for(i = 1; i <= xlen; i++)
  {
  for(j = 1; j<=ylen; j++)
  {
  cout << c[i][j] << " ";
  }
  cout << endl;
  }
  return c[xlen][ylen]; // 最长公共子序列的长度
  }

  /*功能：计算最长公共子序列
  *参数：

•    xlen:字符串x的长度
  

•    ylen:字符串y的长度
  

•    x    :字符串x
  

•    b:标志数组
  

•    current_len:当前长度
  

•    lcs_max_len:最长公共子序列长度
  

  *
  */
  void Display_Lcs(int i, int j, string x, int b[][Y+1],int current_len,int lcs_max_len)
  {
  if (i ==0 || j==0) //如果到达了边界，则可以输出该序列
  {
  for(int s=0; s < lcs_max_len; s++)
  {
  cout << result[s];
  }
  cout<<endl;
  count++; // 最长公共子串个数加1
  return;
  }

  if(b[i][j] == 1) //情况1: x[i-1] == y[j-1]
  {
  current_len--;
  result[current_len]=x[i- 1];
  Display_Lcs(i-1, j-1, x, b,current_len,lcs_max_len);
  }
  else
  {
  if(b[i][j] == 2) // c[i-1][j]
  {
  Display_Lcs(i-1, j, x, b,current_len,lcs_max_len);
  }
  else
  {
  // c[i][j-1]
  
  Display_Lcs(i, j-1, x, b,current_len,lcs_max_len);
  
  }
  }
  }

  int main(int argc, char* argv[])
  {
  string x = "ABCBDABDC";
  string y = "BDCABAC";
  
  int xlen = x.length();
  
  int ylen = y.length();

  int b[X+1][Y+1];

  int lcs_max_len = Lcs_Length( x, y, b, xlen,ylen );
  cout << lcs_max_len << endl;

  Display_Lcs( xlen,ylen, x, b, lcs_max_len, lcs_max_len );
  cout << "共有：" << count << "种";
  return 0;
  }

代码再发一遍，上面的有点问题。

//求取所有的最长公共子序列
#include
using namespace std;

const int X=100, Y= 100; //串的最大长度
char result[X+1]; //用于保存结果
int count= 0; //用于保存公共最长公共子串的个数

/*功能：计算最优值
*参数：

• x:字符串x
• y:字符串y
• b:标志数组
• xlen:字符串x的长度

•    ylen:字符串y的长度
  

  返回值：最长公共子序列的长度
  *
  */
  int Lcs_Length(string x, string y, int b[][Y+1],int xlen,int ylen)
  {
  int i= 0;
  int j= 0;
  int c[X+1][Y+1];
  /

  • 下面两个for循环将第一行和第一列全置为0
    */
    for (i = 0; i<=xlen; i++)
    {
    c[i][0]=0;
    }

    for (i = 0; i <= ylen; i++ )
    {
    c[0][i]=0;
    }

  for (i = 1; i <= xlen; i++)
  {
  
  for (j = 1; j <= ylen; j++)
  {
  if ( x[i-1] == y[j-1] )
  {
  c[i][j] = c[i-1][j-1]+1;
  b[i][j] = 1;
  }
  else // c[i][j] = max( c[i-1][j] , c[i][j-1] )
  {
  if ( c[i-1][j] > c[i][j-1] )
  {
  c[i][j] = c[i-1][j]; // 向上
  b[i][j] = 2;
  }
  else
  {
  if( c[i-1][j] < c[i][j-1] )
  {
  c[i][j] = c[i][j-1]; // 向左
  b[i][j] = 3;
  }
  }
  }
  }
  }
  cout << "计算最优值效果图如下所示：" << endl;
  for(i = 1; i <= xlen; i++)
  {
  for(j = 1; j<=ylen; j++)
  {
  cout << c[i][j] << " ";
  }
  cout << endl;
  }
  return c[xlen][ylen]; // 最长公共子序列的长度
  }

  /*功能：计算最长公共子序列
  *参数：

•    xlen:字符串x的长度
  

•    ylen:字符串y的长度
  

•    x    :字符串x
  

•    b:标志数组
  

•    current_len:当前长度
  

•    lcs_max_len:最长公共子序列长度
  

  *
  */
  void Display_Lcs(int i, int j, string x, int b[][Y+1],int current_len,int lcs_max_len)
  {
  if (i ==0 || j==0) //如果到达了边界，则可以输出该序列
  {
  for(int s=0; s < lcs_max_len; s++)
  {
  cout << result[s];
  }
  cout<<endl;
  count++; // 最长公共子串个数加1
  return;
  }

  if(b[i][j] == 1) //情况1: x[i-1] == y[j-1]
  {
  current_len--;
  result[current_len]=x[i- 1];
  Display_Lcs(i-1, j-1, x, b,current_len,lcs_max_len);
  }
  else
  {
  if(b[i][j] == 2) // c[i-1][j]
  {
  Display_Lcs(i-1, j, x, b,current_len,lcs_max_len);
  }
  else
  {
  // c[i][j-1]
  
  Display_Lcs(i, j-1, x, b,current_len,lcs_max_len);
  
  }
  }
  }

  int main(int argc, char* argv[])
  {
  string x = "ABCBDABDC";
  string y = "BDCABAC";
  
  int xlen = x.length();
  
  int ylen = y.length();

  int b[X+1][Y+1];

  int lcs_max_len = Lcs_Length( x, y, b, xlen,ylen );
  cout << lcs_max_len << endl;

  Display_Lcs( xlen,ylen, x, b, lcs_max_len, lcs_max_len );
  cout << "共有：" << count << "种";
  return 0;
  }

#include
#include
#define MAXLEN 100

void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN])
{
int i, j;

for(i = 0; i <= m; i++)
    c[i][0] = 0;
for(j = 1; j <= n; j++)
    c[0][j] = 0;
for(i = 1; i<= m; i++)
{
    for(j = 1; j <= n; j++)
    {
        if(x[i-1] == y[j-1])
        {
            c[i][j] = c[i-1][j-1] + 1;
            b[i][j] = 0;
        }
        else if(c[i-1][j] >= c[i][j-1])
        {
            c[i][j] = c[i-1][j];
            b[i][j] = 1;
        }
        else
        {
            c[i][j] = c[i][j-1];
            b[i][j] = -1;
        }
    }
}

}

void PrintLCS(int b[][MAXLEN], char *x, int i, int j)
{
if(i == 0 || j == 0)
return;
if(b[i][j] == 0)
{
PrintLCS(b, x, i-1, j-1);
printf("%c ", x[i-1]);
}
else if(b[i][j] == 1)
PrintLCS(b, x, i-1, j);
else
PrintLCS(b, x, i, j-1);
}

int main(int argc, char **argv)
{
char x[MAXLEN] = {"ABCBDAB"};
char y[MAXLEN] = {"BDCABA"};
int b[MAXLEN][MAXLEN];
int c[MAXLEN][MAXLEN];
int m, n;

m = strlen(x);
n = strlen(y);

LCSLength(x, y, m, n, c, b);
PrintLCS(b, x, m, n);

return 0;

}