所有最长的公共子序列

本文介绍了所有最长的公共子序列的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

[注意:我事先搜索过，找不到解决所有子序列LCS问题的建议.]

[NOTE: I searched beforehand and couldn't find advice on solving the LCS problem for all subsequences.]

我在编写最长公共子序列"问题的解决方案时遇到了麻烦，在该问题中，我返回了两个输入字符串的所有最长公共子序列.我查看了维基百科页面，并尝试在其中实施伪代码，但遇到了我的"backtrackAll"方法出现问题.我相信我在下面正确地计算了LCS矩阵，但是我的"backtrackAll"方法返回了一个空集.关于我在做什么的任何提示吗?

I'm having trouble coding up a solution to the "longest common subsequence" problem where I return all the longest common subsequences for two input Strings. I looked at the Wikipedia page and tried to implement the pseudo-code on there, but ran into a problem with my "backtrackAll" method. I believe I'm computing the LCS matrix correctly below, but my "backtrackAll" method returns an empty set. Any tips on what I'm doing wrong?

public static void main (String[] args) { String s1 = "AGCAT"; String s2 = "GAC"; int[][] matrix = computeMatrix(s1,s2); HashSet<String> set = backtrackAll(matrix,s1,s2,s1.length(),s2.length()); //more stuff would go here... } private static int[][] computeMatrix(String s1, String s2) { int[][] C = new int[s1.length()+1][s2.length()+1]; for (int i = 1; i < s1.length()+1; i++) { for (int j = 1; j < s2.length()+1; j++) { if (s1.charAt(i-1) == s2.charAt(j-1)) { C[i][j] = C[i-1][j-1] + 1; } else { C[i][j] = Math.max(C[i][j-1], C[i-1][j]); } } } return C; } private static HashSet<String> backtrackAll(int[][] C, String s1, String s2, int i, int j) { if (i == 0 || j == 0) { return new HashSet<String>(); } else if (s1.charAt(i-1) == s2.charAt(j-1)) { HashSet<String> R = backtrackAll(C,s1,s2,i-1,j-1); HashSet<String> new_set = new HashSet<String>(); for (String Z: R) { new_set.add(Z + s1.charAt(i-1)); } return new_set; } else { HashSet<String> R = new HashSet<String>(); if (C[i][j-1] >= C[i-1][j]) { R = backtrackAll(C, s1, s2, i, j-1); } if (C[i-1][j] >= C[i][j-1]) { R.addAll(backtrackAll(C,s1,s2,i-1,j)); } return R; } }

推荐答案

我对其进行了一些修改.现在可以使用了.您还应该考虑何时返回null HashSet，在这种情况下，必须添加最后一个匹配的字符.

I modified it a bit. It now works. You should also consider when a null HashSet is returned in whose case the last matched character has to be added.

private static HashSet<String> backtrackAll(int[][] C, String s1, String s2, int i, int j) { // System.out.println(i+" " + j); if (i == 0 || j == 0) { // System.out.println("0t"); return new HashSet<String>(); } else if (s1.charAt(i - 1) == s2.charAt(j - 1)) { // System.out.println("2t"); HashSet<String> R = backtrackAll(C, s1, s2, i - 1, j - 1); HashSet<String> new_set = new HashSet<String>(); for (String Z : R) { // System.out.println("1t"); new_set.add(Z + s1.charAt(i - 1)); } new_set.add("" + s1.charAt(i - 1)); return new_set; } else { // System.out.println("3t"); HashSet<String> R = new HashSet<String>(); if (C[i][j - 1] >= C[i - 1][j]) { R = backtrackAll(C, s1, s2, i, j - 1); } if (C[i - 1][j] >= C[i][j - 1]) { R.addAll(backtrackAll(C, s1, s2, i - 1, j)); } return R; } }