数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究用于最长公共子序列的 Java 程序
以下是用于最长公共子序列的 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)。两个“for”循环在两个字符串的长度上迭代，如果“i”和“j”都是 0，则数组的特定索引将被分配为 0。否则，将构建 my_arr[第一个字符串的长度 +1][第二个字符串的长度 +1]。</p>
主函数定义了 Demo 类的新的实例，并定义了两个字符串 my_str_1 和 my_str_2。两个字符串都将转换为数组，其长度存储在单独的变量中。该函数在这些值上被调用。</p>
这是一项动态规划技术，其中一个值被计算并存储在一个数组内，无需像在递归中那样反复计算它。只要需要一个先前计算过的元素，它就会从数组中获取。</p>
更新日期： 2020-07-04
273 次浏览
广告