Chương trình Java dãy con chung dài nhất (LCS)

Dưới đây là chương trình Java cho dãy con chung dài nhất:

Ví dụ

public class Demo{ 
    int subseq(char[] a, char[] b, int a_len, int b_len){ 
        int my_arr[][] = new int[a_len + 1][b_len + 1]; 
        for (int i = 0; i <= a_len; i++){ 
            for (int j = 0; j <= b_len; j++){ 
                if (i == 0 || j == 0) 
                    my_arr[i][j] = 0; 
                else if (a[i - 1] == b[j - 1]) 
                    my_arr[i][j] = my_arr[i - 1][j - 1] + 1; 
                else 
                    my_arr[i][j] = max_val(my_arr[i - 1][j], my_arr[i][j - 1]); 
            } 
        } 
        return my_arr[a_len][b_len]; 
    } 
    int max_val(int val_1, int val_2){ 
        return (val_1 > val_2) ? val_1 : val_2; 
    } 
    public static void main(String[] args){ 
        Demo my_inst = new Demo(); 
        String my_str_1 = "MNSQR"; 
        String my_str_2 = "PSQR"; 
        char[] a = my_str_1.toCharArray(); 
        char[] b = my_str_2.toCharArray(); 
        int a_len = a.length; 
        int b_len = b.length; 
        System.out.println("Độ dài dãy con chung dài nhất là: " + my_inst.subseq(a, b, a_len, b_len)); 
    } 
}

Kết quả

Độ dài dãy con chung dài nhất là 3

Lớp Demo chứa hàm subseq trả về dãy con chung dài nhất cho các chuỗi cho trước. Hai vòng for lặp qua độ dài cả hai chuỗi. Nếu cả i và j bằng 0, chỉ số mảng gán 0. Ngược lại, my_arr[len1+1][len2+1] được xây dựng.

Hàm main định nghĩa instance mới của Demo và hai chuỗi. Cả hai chuyển thành mảng và độ dài lưu trong biến riêng. Hàm được gọi trên các giá trị này. Đây là kỹ thuật quy hoạch động - giá trị tính trước lưu trong mảng, tránh tính lại như đệ quy.