Chương trình Java tìm dãy con đối xứng dài nhất (Longest Palindromic Subsequence)

Đối với dãy con đối xứng dài nhất, mã Java như sau:

Ví dụ

public class Demo { 
    static String longest_seq(String str_1, String str_2) { 
        int str_1_len = str_1.length(); 
        int str_2_len = str_2.length(); 
        char str_1_arr[] = str_1.toCharArray(); 
        char str_2_arr[] = str_2.toCharArray(); 
        int L[][] = new int[str_1_len + 1][str_2_len + 1]; 
        for (int i = 0; i <= str_1_len; i++) { 
            for (int j = 0; j <= str_2_len; j++) { 
                if (i == 0 || j == 0) { 
                    L[i][j] = 0; 
                } else if (str_1_arr[i - 1] == str_2_arr[j - 1]) { 
                    L[i][j] = L[i - 1][j - 1] + 1; 
                } else { 
                    L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]); 
                } 
            } 
        } 
        int my_index = L[str_1_len][str_2_len]; 
        char[] longest_seq = new char[my_index + 1]; 
        int i = str_1_len, j = str_2_len; 
        while (i > 0 && j > 0) { 
            if (str_1_arr[i - 1] == str_2_arr[j - 1]) { 
                longest_seq[my_index - 1] = str_1_arr[i - 1]; 
                i--; 
                j--; 
                my_index--; 
            } else if (L[i - 1][j] > L[i][j - 1]) { 
                i--; 
            } else { 
                j--; 
            } 
        } 
        String my_result = ""; 
        for (int x = 0; x < longest_seq.length; x++) { 
            my_result += longest_seq[x]; 
        } 
        return my_result; 
    } 
    static String longestPalSubseq(String str) { 
        String rev_str = str; 
        rev_str = reverse_str(rev_str); 
        return longest_seq(str, rev_str); 
    } 
    static String reverse_str(String str) { 
        String my_result = ""; 
        char[] trial = str.toCharArray(); 
        for (int i = trial.length - 1; i >= 0; i--) { 
            my_result += trial[i]; 
        } 
        return my_result; 
    } 
    public static void main(String[] args) { 
        String str = "HelloHelloo"; 
        System.out.println("Longest palindromic subsequence is"); 
        System.out.println(longestPalSubseq(str)); 
    } 
}

Kết quả

Longest palindromic subsequence is llell

Một lớp tên Demo chứa hàm 'longest_seq' khai báo hai chuỗi và hai mảng ký tự. Các mảng sẽ được lặp qua, và dãy đối xứng dài nhất được tìm thấy, bằng kỹ thuật quy hoạch động. Trong phương pháp này, một khi giá trị cho mảng cụ thể được tìm thấy, nó được lưu trữ và không tính toán lại, làm cho việc tính toán hiệu quả.

Hàm 'longestPalSubseq' nhận chuỗi làm tham số, đảo ngược chuỗi và gọi hàm 'longest_seq' bằng cách truyền chuỗi đảo ngược. Hàm khác tên 'reverse_str' dùng để đảo ngược chuỗi được truyền làm tham số. Trong hàm main, chuỗi được định nghĩa, và hàm 'longestPalSubseq' được gọi, và đầu ra được hiển thị trên console.