LCS算法（例如）

问题描述

有一个动态规划算法找到两个序列的最长公共子。我如何才能找到两个序列X和Y的LCS算法（正确性测试）

 （一）X = ABEDFEESTYH Y = ABEDFEESTYHABCDF

（二）X = BFAAAABBBBBJPRSTY Y = ABCDEFGHIJKLMNOPRS

（三）X =φ（空序列），Y = BABADCAB
 

解决方案

下面是一个在线计算器

http://igm.univ-mlv.fr/~lecroq/ seqcomp / node4.html

Java的

 公共类LCS {

    公共静态无效的主要（字串[] args）{
        字符串x = StdIn.readString（）;
        字符串Y = StdIn.readString（）;
        INT M = x.length（）;
        INT N = y.length（）;

        //选择[I] [J] = X [i..M]和Y的LCS [j..N]的长度
        INT [] [] =选择新INT [M + 1] [N + 1];

        //计算LCS的长度，并通过动态规划的所有子问题
        的for（int i = M-1; I＆GT; = 0;我 - ）{
            对于（INT J = N-1，J＆GT; = 0; j--）{
                如果（x.charAt（I）== y.charAt（J））
                    选择[I] [j]的选择= [I + 1] [J + 1〕+ 1;
                其他
                    选择[I] [J] = Math.max（OPT [I + 1] [J]，选择[I] [J + 1]）;
            }
        }

        //恢复LCS本身并打印到标准输出
        INT I = 0，J = 0;
        而（ⅰ＆其中，M＆安培;＆安培; J＆其中N）{
            如果（x.charAt（ⅰ）== y.charAt（j）条）{
                System.out.print（x.charAt（ⅰ））;
                我++;
                J ++;
            }
            否则，如果（选择[​​I + 1] [J]≥= OPT [I] [J + 1]）我++;
            否则J ++;
        }
        的System.out.println（）;

    }

}
 

There's a dynamic programming algorithm to find the Longest Common Subsequence of two sequences. How can I find the LCS algorithm of two sequences X and Y. (Test of correctness)

(a)   X  = ABEDFEESTYH  Y=ABEDFEESTYHABCDF

(b)  X =  BFAAAABBBBBJPRSTY  Y=ABCDEFGHIJKLMNOPRS

(c)  X = ϕ (Empty Sequence), Y = BABADCAB

解决方案

Here is an online calculator

http://igm.univ-mlv.fr/~lecroq/seqcomp/node4.html

Java

public class LCS {

    public static void main(String[] args) {
        String x = StdIn.readString();
        String y = StdIn.readString();
        int M = x.length();
        int N = y.length();

        // opt[i][j] = length of LCS of x[i..M] and y[j..N]
        int[][] opt = new int[M+1][N+1];

        // compute length of LCS and all subproblems via dynamic programming
        for (int i = M-1; i >= 0; i--) {
            for (int j = N-1; j >= 0; j--) {
                if (x.charAt(i) == y.charAt(j))
                    opt[i][j] = opt[i+1][j+1] + 1;
                else 
                    opt[i][j] = Math.max(opt[i+1][j], opt[i][j+1]);
            }
        }

        // recover LCS itself and print it to standard output
        int i = 0, j = 0;
        while(i < M && j < N) {
            if (x.charAt(i) == y.charAt(j)) {
                System.out.print(x.charAt(i));
                i++;
                j++;
            }
            else if (opt[i+1][j] >= opt[i][j+1]) i++;
            else                                 j++;
        }
        System.out.println();

    }

}

这篇关于LCS算法（例如）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！