다음은 Longest Common Subsequence에 대한 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라는 클래스에는 주어진 문자열, 즉 str_1[0 to len(str_1-1) , str_2(0 to len(str_2-1) //2 'for' 루프)에 대해 가장 긴 공통 부분 시퀀스를 반환하는 "subseq"라는 함수가 포함되어 있습니다. 두 문자열의 길이에 대해 반복되고 'i'와 'j'가 모두 0이면 배열의 특정 인덱스가 0으로 할당됩니다. 그렇지 않으면 my_arr[첫 번째 문자열의 길이 +1][두 번째 문자열의 길이 + 1]이 구축되었습니다.
주 함수는 Demo 클래스의 새 인스턴스를 정의하고 두 개의 문자열 my_str_1 및 my_str_2를 정의합니다. 두 문자열 모두 배열로 변환되고 해당 길이는 별도의 변수에 저장됩니다. 이 값에 대해 함수가 호출됩니다.
이것은 하나의 값을 계산하여 배열에 저장하는 동적 프로그래밍 기법으로, 재귀에서처럼 반복해서 계산할 필요가 없습니다. 이전에 계산된 요소가 필요할 때마다 배열에서 가져옵니다.