Đối với dãy con Palindromic 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));
}
} Đầu ra
Longest palindromic subsequence is llell
Một lớp có tên Demo chứa hàm ‘long_seq’ khai báo hai chuỗi và hai mảng ký tự. Các mảng sẽ được lặp lại và chuỗi palindromic dài nhất được tìm thấy, bằng cách sử dụng kỹ thuật lập trình động. Trong phương pháp này, khi giá trị của một mảng cụ thể được tìm thấy, nó sẽ được lưu trữ và không phải tính toán lại, do đó làm cho việc tính toán trở nên hiệu quả.
Một hàm có tên là ‘longPalSubseq’ nhận chuỗi làm tham số và đảo ngược chuỗi và gọi hàm ‘long_seq’ bằng cách chuyển chuỗi đã đảo ngược. Một hàm khác có tên là ‘reverse_str’ được sử dụng để đảo ngược chuỗi được truyền dưới dạng tham số cho hàm. Trong hàm chính, chuỗi được xác định và hàm ‘longPalSubseq’ được gọi và kết quả đầu ra được hiển thị trên biểu tượng.