데이터 구조 와 알고리즘 자바 버 전 - LCS 최 장 서브 시퀀스

5742 단어 데이터 구조 및 알고리즘 자바자바알고리즘LCS
오늘 공 유 된 내용 은 LCS, 최 장자 서열 로 개인 적 으로 이 알고리즘 책 을 읽 는 것 이 편리 하 다.여기 코드 바로 붙 여.
public class LCS {

    /**
     *            
     * @param a
     * @param b
     * @return
     */
    public int getLCSLength(String a, String b) {
        /**
         * row ，line 
         */
        int line = a.length();
        int row = b.length();
        /**
         * A   B  
         */
        char[] A = a.toCharArray();
        char[] B = b.toCharArray();
        //        0，       
        int[][] dp = new int[line + 1][row + 1];
        //   ，      0
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = 0;
        }
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 0;
        }

        for (int m = 1; m < line + 1; m++) {
            for (int n = 1; n < row + 1; n++) {
                if (A[m - 1] == B[n - 1]) {
                    //        
                    dp[m][n] = dp[m - 1][n - 1] + 1;
                } else {
                    //        
                    dp[m][n] = Math.max(dp[m - 1][n], dp[m][n - 1]);
                }
            }
        }
        for (int i = 0; i < line; i++) {
            for (int j = 0; j < row; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        //       
        printLCS(line - 1, row - 1, A, B, dp);
        return dp[line - 1][row - 1];
    }

    /**
     * 
     * @param i   
     * @param j   
     * @param A               
     * @param dp   
     */
    public void printLCS(int i, int j, char[] s1, char[] s2, int[][] dp) {
        LinkedList stack = new LinkedList<>();
        while ((i >= 0) && (j >= 0)) {
            if (s1[i] == s2[j]) {
                //          ，    ，     
                stack.push(s1[i]);
                i--;
                j--;
            } else {
                if (dp[i + 1][j] > dp[i][j + 1]) {
                    j--;
                } else {
                    i--;
                }
            }
        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop());
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LCS lcs = new LCS();
        System.out.println(lcs.getLCSLength("xich", "ixafh"));
    }

}
HDU 4505 작은 Q 시리즈 - 엘리베이터 안의 사랑
자바 에서 시간 제어 에 관 한 조작

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage