最长公共子序列的 Java 程序

javaobject oriented programmingprogramming更新于 2025/7/13 14:04:17

以下是最长公共子序列的 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("最长公共子序列的长度为"+ " " + my_inst.subseq(a, b, a_len,       b_len));
   }
}

输出

最长公共子序列的长度为 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[第一个字符串的长度 +1][第二个字符串的长度 +1]。

主函数定义了 Demo 类的一个新实例，并定义了两个字符串 my_str_1 和 my_str_2。两个字符串都转换为数组，它们的长度存储在单独的变量中。这些值将调用该函数。

这是一种动态规划技术，其中计算一个值并将其存储在数组中，无需像递归那样一次又一次地计算它。每当需要先前计算的元素时，就会从数组中获取它。