ต่อไปนี้เป็นโปรแกรม Java สำหรับลำดับรองร่วมที่ยาวที่สุด -
ตัวอย่าง
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));
}
} ผลลัพธ์
The length of the longest common subsequence is 3
คลาสชื่อ Demo มีฟังก์ชันที่เรียกว่า "subseq" ซึ่งส่งคืนลำดับย่อยทั่วไปที่ยาวที่สุดสำหรับสตริงที่กำหนด เช่น str_1[0 ถึง len(str_1-1) , str_2(0 ถึง len(str_2-1) //2 'for' ลูป มีการวนซ้ำตลอดความยาวของสตริงทั้งสอง และหากทั้ง 'i' และ 'j' เป็น 0 ดัชนีเฉพาะของอาร์เรย์จะถูกกำหนดเป็น 0 มิฉะนั้น my_arr[length of first string +1][length of second string + 1] ถูกสร้างขึ้น
ฟังก์ชันหลักกำหนดอินสแตนซ์ใหม่ของคลาสสาธิตและกำหนดสองสตริง my_str_1 และ my_str_2 สตริงทั้งสองจะถูกแปลงเป็นอาร์เรย์และความยาวของสตริงจะถูกเก็บไว้ในตัวแปรแยกกัน ฟังก์ชันนี้ถูกเรียกใช้ตามค่าเหล่านี้
นี่เป็นเทคนิคการเขียนโปรแกรมแบบไดนามิกที่มีการคำนวณและจัดเก็บค่าหนึ่งค่าในอาร์เรย์ ทำให้ไม่จำเป็นต้องคำนวณซ้ำแล้วซ้ำอีกเหมือนกับการเรียกซ้ำ เมื่อใดก็ตามที่จำเป็นต้องใช้องค์ประกอบที่คำนวณไว้ก่อนหน้านี้ องค์ประกอบนั้นจะถูกดึงมาจากอาร์เรย์
