Longest Common Subsequence in Java

by Online Tutorials Library July 22, 2022

Longest Common Subsequence in Java

The longest subsequence common to all the given sequences is referred to as Longest Common Subsequence. The reason for using the LCS is to restrict the element of the subsequences from occupying the consecutive position within the original sequences.

A sequence that appears in the same relative order, either contiguous or non-contiguous way is known as a subsequence.

For example, if we have two sequences, such as “KTEURFJS” and “TKWIDEUJ”, the longest common subsequence will be “TEUJ” of length 4.

In Java, there are two ways to implement the LSC program, i.e., using the recursive method and using dynamic programming. Both the ways have a different implementation.

Longest Common Subsequence in Java

Using Dynamic Programming

This approach is a tabulated implementation for the Longest Common Subsequence. In order to find the Longest Common Subsequence, we use the following steps:

First, we create a table of dimensions (p + 1)*(q + 1) where p and q are the lengths of the given sequences. In the created table, we set 0 to the first row and the first column.
All the remaining cells of the table are filled by using the following steps:
1. If the characters of the corresponding row and the column are the same and matched successfully, fill the current cell with 1 to the diagonal element and point an arrow to the diagonal cell.
2. If the characters are not matched, we fill the current cell with the value of the previous column and previous row element. The arrow points to the cell having maximum value, and when the value in both the cells is equal, the arrow will point to any of them.
3. We repeat step 2 until the complete table is not filled.
4. The length of the longest common subsequence is the value present in the last row and the last column.
5. In order to get the LCS, we follow the direction of the arrow from the last element. The elements corresponding to the brackets() are form the longest common subsequence.

Let’s implement the code of the Longest Common Subsequence using dynamic programming by following the above steps.

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] = ‘

Longest Common Subsequence in Java

Longest Common Subsequence in Java

Using Dynamic Programming

Lombok Java

Polygonal Number in Java

You may also like