开发者社区 问答 正文

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

//求取所有的最长公共子序列
不知道代码哪里写错了,也只有一个币能悬赏,希望有空的大神们帮忙看看,纠结好久了不知道怎么改。
#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;
}

展开
收起
a123456678 2016-03-20 09:41:34 3602 分享 版权
1 条回答
写回答
取消 提交回答
  • #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;
    }
    
    
    2019-07-17 19:08:39
    赞同 展开评论
问答分类:
BI
问答地址: