本文介绍了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> = 0;我 - ){
            对于(INT J = N-1,J> = 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算法(例如)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

10-28 18:12