java - 最长公共(public)子序列函数并不适用于所有示例

Question

编辑:向上

该代码无法与下面的字符串一起正常工作。

"1 11 23 1 18 9 15 23 5"

"11 1 18 1 20 5 11 1"

编辑:我注意到，如果我将第二个字符串中的 20 更改为 40，该函数将正常工作...

对于字符串:

"12 4 55 11 8 43 22 90 5 88 15"

"15 66 4 36 43 22 78 88 32"

它工作正常。哪里有问题？

这是我的代码:

 int[][] tabelka = new int[linia1.length()+1][linia2.length()+1];


        for (int i = 0; i<linia1.length(); i++) {
            for (j = 0; j<linia2.length(); j++) {

                if ( linia1.charAt(i) == linia2.charAt(j) ) {
                    tabelka[i+1][j+1] = tabelka[i][j] + 1;
                }

                else {
                    tabelka[i+1][j+1] = Math.max(tabelka[i+1][j], tabelka[i][j+1]);
                }

            }
        }

        for (int i = 0; i<linia1.length(); i++) {
            for (j = 0; j<linia2.length(); j++) {
                System.out.println(tabelka[i][j]);
            }
        }

        StringBuffer podciag = new StringBuffer();

        for(int x = linia1.length(), y = linia2.length(); x != 0 && y != 0; ) {

            if( tabelka[x][y] == tabelka[x-1][y] ) {
                licznik++;
                x--;
            }

            else if( tabelka[x][y] == tabelka[x][y-1] ) {
                licznik++;
                y--;
            }

            else {
                licznik++;
                assert linia1.charAt(x-1) == linia2.charAt(y-1);
                podciag.append(linia1.charAt(x-1));
                x--;
                y--;
            }
        }

        String buff = podciag.reverse().toString();

此代码的输出(对于前两个字符串)是:

11 1 18 1 2 5

但是，输出应该是:

11 1 18 5

Answer 1

有关完整/更好的解释，请参阅:

• http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

• http://www.geeksforgeeks.org/printing-longest-common-subsequence/

我认为您正在正确构建数组。但是，我不确定构建 LCS 时读取该表的方式。

这个想法是从二维数组解决方案的末尾开始[str1.length()][str2.length()]并且如果:

• str1 和 str2 的最后一个字符相等，则最后一个字符是 LCS 的一部分，并递减两个索引
• 如果不相等，则比较解决方案[i-1][j]和解决方案[i][j-1]，并朝值较大的方向前进。
• 重复此操作，直到任一索引为 0。