Sau đây là chương trình Java cho Chuỗi 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("The length of the longest common subsequence is"+ " " + my_inst.subseq(a, b, a_len, b_len));
}
} Đầu ra
The length of the longest common subsequence is 3
Một lớp có tên Demo chứa một hàm được gọi là "subsq" trả về dãy con chung dài nhất cho các chuỗi đã cho, tức là str_1 [0 to len (str_1-1), str_2 (0 to len (str_2-1) // 2 'for' vòng lặp được lặp lại trên độ dài của cả hai chuỗi và nếu cả 'i' và 'j' đều bằng 0, thì các chỉ số cụ thể của mảng được gán cho 0. Nếu không, my_arr [độ dài của chuỗi đầu tiên +1] [độ dài của chuỗi thứ hai + 1] được xây dựng.
Hàm main định nghĩa một phiên bản mới của lớp Demo và xác định hai chuỗi my_str_1 và my_str_2. Cả hai chuỗi đều được chuyển đổi thành mảng và độ dài của chúng được lưu trữ trong các biến riêng biệt. Hàm được gọi trên các giá trị này.
Đây là kỹ thuật lập trình động, trong đó một giá trị được tính toán và lưu trữ trong một mảng, loại bỏ nhu cầu tính toán nó nhiều lần như trong đệ quy. Bất cứ khi nào một phần tử đã tính toán trước đó được yêu cầu, nó sẽ được tìm nạp từ mảng.