Java中的最长公共子序列

2025年5月6日 | 阅读4分钟

所有给定序列的最长公共子序列被称为最长公共子序列。使用LCS的原因是为了限制子序列的元素在原始序列中占据连续的位置。

一个以相同相对顺序出现的序列，无论是连续还是非连续的，都称为子序列。

例如，如果我们有两个序列，如“KTEURFJS”和“TKWIDEUJ”，那么最长公共子序列将是“TEUJ”，长度为4。

在Java中，有两种方法可以实现LSC程序，即使用递归方法和使用动态规划。这两种方法都有不同的实现方式。

使用动态规划

这种方法是一种表格化的最长公共子序列实现。为了找到最长公共子序列，我们使用以下步骤

首先，我们创建一个尺寸为 (p + 1)*(q + 1) 的表格，其中 p 和 q 是给定序列的长度。在创建的表格中，我们将第一行和第一列设置为0。
表格的所有剩余单元格都通过使用以下步骤填充
1. 如果相应行和列的字符相同并且成功匹配，则用1填充当前单元格到对角线元素，并将一个箭头指向对角线单元格。
2. 如果字符不匹配，我们用前一列和前一行元素的值填充当前单元格。箭头指向具有最大值的单元格，当两个单元格的值相等时，箭头将指向其中任何一个。
3. 我们重复步骤2，直到整个表格被填充完毕。
4. 最长公共子序列的长度是最后一行和最后一列的值。
5. 为了获得LCS，我们遵循从最后一个元素开始的箭头方向。对应于括号()的元素构成了最长公共子序列。

让我们通过遵循上述步骤，使用动态规划来实现最长公共子序列的代码。

LCSExample1.java

// import required classes and packages
import Java.util.*; 
import java.io.*; 
import java.util.Scanner;

// create LCSExample1 class to find the Longest Common Subsequence
class LCSExample1 {
	
	// create findLengthOfLCS() method that returns the longest common sequences
	public static String findLengthOfLCS(String str1, String str2, int p, int q) {
    
		// create a matrix which act as a table for LCS
		int[][] tableForLCS = new int[p + 1][q + 1];

		// fill the table in the bottom up way
		for (int i = 0; i <= p; i++) {
			for (int j = 0; j <= q; j++) {
				if (i == 0 || j == 0)
					tableForLCS[i][j] = 0;	// Fill each cell corresponding to first row and first column with 0
				else if (str1.charAt(i - 1) == str2.charAt(j - 1))
					tableForLCS[i][j] = tableForLCS[i - 1][j - 1] + 1;	// add 1 in the cell of the previous row and column and fill the current cell with it 
				else
					tableForLCS[i][j] = Math.max(tableForLCS[i - 1][j], tableForLCS[i][j - 1]);	//find the maximum value from the cell of the previous row and current column and the cell of the current row and previous column  
			}
		}
	
		int index = tableForLCS[p][q];
		int temp = index;

		char[] longestCommonSubsequence = new char[index + 1];
		longestCommonSubsequence[index] = '\0';

		int i = p, j = q;
		String lcs ="";
		while (i > 0 && j > 0) {
			if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
				
				longestCommonSubsequence[index - 1] = str1.charAt(i - 1);
				i--;
				j--;
				index--;
			}
			else if (tableForLCS[i - 1][j] > tableForLCS[i][j - 1])
				i--;
			else
				j--;
		}
		
		for (int k = 0; k <= temp; k++)
			lcs = lcs + longestCommonSubsequence[k];
			
		return lcs;
	}
	public static void main(String[] args) {
		
		String str1, str2, LCS;
		
		Scanner sc= new Scanner(System.in); //System.in is a standard input stream.
		System.out.print("Enter first sequence: ");
		str1 = sc.nextLine(); //reads string.
		
		System.out.print("Enter second sequence: ");
		str2 = sc.nextLine(); //reads string.
		
		int p = str1.length();
		int q = str2.length();
		
		LCS = findLengthOfLCS(str1, str2, p, q);
		
		System.out.print("Sequence1: " + str1 + "\nSequence2: " + str2);
		System.out.println("\nLCS: "+LCS);
		
	}
}

输出

使用递归实现

让我们通过一个使用递归实现的LCS的例子来理解。在这个例子中，我们从用户那里获取两个序列，并返回或打印最长公共子序列的长度。

LCSExample2.java

// import required classes and packages
import java.util.*; 
import java.io.*; 
import java.util.Scanner;

// create LCSExample2 class to find the length of the Longest Common Subsequence
public class LCSExample2 {
  
    // create getLengthOfLCS() method that returns length of the LCS
    public static int getLengthOfLCS(char[] str1, char[] str2, int p, int q)
    {
		//check the length of the sequence
        if (p == 0 || q == 0)
            return 0;
		
		// when the last character of both the sequences are equal
        if (str1[p - 1] == str2[q - 1])
            return 1 + getLengthOfLCS(str1, str2, p - 1, q - 1);
        else
            return maxValue(getLengthOfLCS(str1, str2, p, q - 1), getLengthOfLCS(str1, str2, p - 1, q));
    }
  
    // create maxValue() method that returns the length of the sequence having maximum length from both of them 
    static int maxValue(int length1, int length2)
    {
        if (length1 > length2)
			return length1;
		else
			return length2;
    }
	
	//main() method starts
    public static void main(String[] args)
    {
        String string1, string2;
		
		//create Scanner class object to get sequence from the user
		Scanner sc = new Scanner(System.in); //System.in is a standard input stream.
		System.out.print("Enter first sequence: ");
		string1 = sc.nextLine(); //reads string.
		
		System.out.print("Enter second sequence: ");
		string2 = sc.nextLine(); //reads string.
		
		char[] str1 = string1.toCharArray();
        char[] str2 = string2.toCharArray();
		
		int p = string1.length();
		int q = string2.length();
  
        System.out.println("Length of the Longest Common Subsequence is: "+ getLengthOfLCS(str1, str2, p, q));
    }
}

输出

下一个主题Tree-boundary-traversal-in-java

Java中的最长公共子序列

使用动态规划

使用递归实现

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java中的最长公共子序列

使用动态规划

使用递归实现

相关帖子

Java 中通过更改最多 K 位数字构造最大回文数

Java 中的二维数组排序

Java 中的一维数组

在 Java 中获取本地 IP 地址

Stern-Brocot Sequence in Java

Sphenic Number in Java

Java 代码片段

Advantages of Inheritance in Java

Java 中将字节转换为无符号字节

Java 8 和 Java 9 的区别

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器