如何为最长公共子序列打印所有可能的解决方案 [英] How to print all possible solutions for Longest Common subsequence

问题描述

我想打印所有可能的解决LCS问题的方法.

I want to print all the possible solutions to LCS problem.

两个字符串abcbdab和bdcaba应该打印以下3个字符串: bdab，bcba，bcab.

The two strings abcbdab and bdcaba should print following 3 strings: bdab,bcba,bcab.

C是全局矩阵表，该表根据算法获取值，m，n是序列a，b的长度.

C is the global matrix table which takes values according to algorithm and m, n are the length of the sequences a, b.

但是输出结果出乎意料.

But The output is something unexpected.

#include<stdio.h>
#include<conio.h>
int co=0,m=0,n=0,c[10][10];
char a[10],b[10];
void main()
{
    int i,j;
    clrscr();
    printf("Enter Two strings: ");
    scanf("%s",a);
    scanf("%s",b);
    m=strlen(a);
    n=strlen(b);
    for(i=0;i<=m;i++)
    {
        for(j=0;j<=n;j++)
        {   if(i==0 || j==0)
            {
                c[i][j]=0;
            }
            else if(a[i-1]==b[j-1])
            {
                c[i][j]=c[i-1][j-1]+1;
            }
            else if(c[i-1][j]>=c[i][j-1])
            {
                c[i][j]=c[i-1][j];
            }
            else
            {
                c[i][j]=c[i][j-1];
            }
        }
    }
    for(i=0;i<=m;i++)
    {
        for(j=0;j<=n;j++)
        {
            printf("%d\t",c[i][j]);
        }
        printf("\n");
    }
    print(m,n);
    getch();
}
print(int i,int j)
{
    if(i==0 || j==0)
        return 0;
    else if(a[i-1]==b[j-1])
    {
        print(i-1,j-1);
        if(co==c[m][n])
        {
            co=0;
            printf("\n");
        }
        printf("%c",a[i-1]);
        co++;
    }
    else if(c[i-1][j]==c[i][j-1])
    {
        print(i-1,j);
        print(i,j-1);
    }
    else if(c[i][j-1]>=c[i-1][j])
        print(i,j-1);
    else
        print(i-1,j);
    return;
}

推荐答案

在这里您可以找到有关此操作的递归方法:

Here you can find a recursive approach of how to do this: Reading out all LCSs

这是我使用Java编写此方法的代码:

Here is my code for this approach in Java:

private Set<String> lcs(int[][] dp, String fst, String snd, int i, int j) {
    Set<String> lcss = new HashSet<>();

    if (i == 0 || j == 0) {
        lcss.add("");
    } else if (fst.charAt(i - 1) == snd.charAt(j - 1)) {
        for (String lcs : lcs(dp, fst, snd, i - 1, j - 1)) {
            lcss.add(lcs + fst.charAt(i - 1));
        }
    } else {
        if (dp[i - 1][j] >= dp[i][j - 1]) {
            lcss.addAll(lcs(dp, fst, snd, i - 1, j));
        }

        if (dp[i][j - 1] >= dp[i - 1][j]) {
            lcss.addAll(lcs(dp, fst, snd, i, j - 1));
        }
    }
    return lcss;
}

这篇关于如何为最长公共子序列打印所有可能的解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！