本文介绍了如何为最长公共子序列打印所有可能的解决方案的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我想打印所有可能的解决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;
}

推荐答案

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

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;
}

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

10-15 04:36