1

如何显示两个子串的最长公共子串的所有子串我知道计算 lcs 长度的 dp 方法但是如何显示 lcs 的所有这些 lcs 代码

       function LCSLength(X[1..m], Y[1..n])
C = array(0..m, 0..n)
for i := 0..m
   C[i,0] = 0
for j := 0..n
   C[0,j] = 0
for i := 1..m
    for j := 1..n
        if X[i] = Y[j]
            C[i,j] := C[i-1,j-1] + 1
        else
            C[i,j] := max(C[i,j-1], C[i-1,j])
return C[m,n]

我在网上找不到一篇关于如何找到所有 lcs 的好文章

字符串 1=abcabcaa 字符串 2=acbacba

所有 lcs

ababa abaca abcba

我已经知道计算 lcs 的 dp 方法，任何帮助将不胜感激

我在维基上找到了这个

             function backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j)
  if i = 0 or j = 0
    return {""}
    else if X[i] = Y[j]
    return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)}
   else
    R := {}
    if C[i,j-1] ≥ C[i-1,j]
        R := backtrackAll(C, X, Y, i, j-1)
    if C[i-1,j] ≥ C[i,j-1]
        R := R ∪ backtrackAll(C, X, Y, i-1, j)
    return R

但我很难理解它

4

3 回答 3

2

一个非常直观的方法是存储额外的二维数组反向指针，即：

BP[i,j] := [(i-1,j-1)] if C[i,j] was created from C[i-1,j-1] (there was a match)
BP[i,j] := [(i,j-1), (i-1,j)] if C[i,j] could came from C[i,j-1] or C[i-1,j]
BP[i,j] := [(i,j-1)] if C[i,j] was created from C[i,j-1]
BP[i,j] := [(i-1,j)] if C[i,j] was created from C[i-1,j]

现在，让我们定义一个有向图。数组 C 中的任何条目[i,j]都对应于一个顶点，而反向指针对应于边。

有n*m顶点，最多有2*n*m边，因为一个顶点最多有 2 个反向指针。

现在的问题是返回该图中从 vertex[n,m]到 vertex的所有路径[0,0]。

该图是有向的并且没有循环，因此您可以简单地跟随 DFS 的指针（不将顶点标记为已访问），并为每条边([i,j] -> [i-1,j-1])附加与此匹配对应的字母到结果字符串。LCS是到达[0,0]顶点后累积的字符串。

于 2013-08-29T00:07:30.900 回答
0

这是 LCS 最简单的 java 程序：-

导入 java.util.Scanner；

公共类 StrCmp {

public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    System.out.println("Enter the string");
    String s1=s.nextLine();
    String s2=s.nextLine();
    String temp = "";
    char[] a = s1.toCharArray();
    char[] b= s2.toCharArray();
    for(int i=0;i<a.length;i++)
    {
        for(int j=0;j<b.length;j++)
        {
            if(s1.charAt(i)==s2.charAt(j))
            {   
                if(temp.contains(String.valueOf(s2.charAt(j)))){
                    break;
                }
                temp = temp + s2.charAt(j);
            }   
        }   
    }
    System.out.println(temp);
    }

}

于 2015-03-16T20:58:45.757 回答
-1

每个 c[i,j] 条目仅依赖于其他三个 c 表条目：c[i-1,j-1]、c[i-1,j] 和 c[i,j-1]。给定 c[i,j] 的值，我们可以在 O(1) 时间内确定这三个值中的哪一个用于计算 c[i,j]。当前 3 个点有多个可能的值时，可能会有不同的值，即它们相同且在同一点最高。然后，您将不得不考虑它们中的每一个。

于 2013-08-29T04:21:32.413 回答