Java Program to Find the Longest Subsequence Common to All Sequences in a Set of Sequences

This is a java program to implement LCS. The longest common subsequence (LCS) problem is to find the longest subsequence common to all sequences in a set of sequences (often just two). (Note that a subsequence is different from a substring, for the terms of the former need not be consecutive terms of the original sequence.) It is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in bioinformatics.

Here is the source code of the Java Program to Find the Longest Subsequence Common to All Sequences in a Set of Sequences. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1.  
  2. package com.sanfoundry.setandstring;
  3.  
  4. import java.io.BufferedReader;
  5. import java.io.InputStreamReader;
  6. import java.io.IOException;
  7.  
  8. public class LongestCommonSubsequencetoSequences
  9. {
  10.     public static String lcs(String[] strings)
  11.     {
  12.         if (strings.length == 0)
  13.             return "";
  14.         if (strings.length == 1)
  15.             return strings[0];
  16.         int max = -1;
  17.         int cacheSize = 1;
  18.         for (int i = 0; i < strings.length; i++)
  19.         {
  20.             cacheSize *= strings[i].length();
  21.             if (strings[i].length() > max)
  22.                 max = strings[i].length();
  23.         }
  24.         String[] cache = new String[cacheSize];
  25.         int[] indexes = new int[strings.length];
  26.         for (int i = 0; i < indexes.length; i++)
  27.             indexes[i] = strings[i].length() - 1;
  28.         return lcsBack(strings, indexes, cache);
  29.     }
  30.  
  31.     public static String lcsBack(String[] strings, int[] indexes, String[] cache)
  32.     {
  33.         for (int i = 0; i < indexes.length; i++)
  34.             if (indexes[i] == -1)
  35.                 return "";
  36.         boolean match = true;
  37.         for (int i = 1; i < indexes.length; i++)
  38.         {
  39.             if (strings[0].charAt(indexes[0]) != strings[i].charAt(indexes[i]))
  40.             {
  41.                 match = false;
  42.                 break;
  43.             }
  44.         }
  45.         if (match)
  46.         {
  47.             int[] newIndexes = new int[indexes.length];
  48.             for (int i = 0; i < indexes.length; i++)
  49.                 newIndexes[i] = indexes[i] - 1;
  50.             String result = lcsBack(strings, newIndexes, cache)
  51.                     + strings[0].charAt(indexes[0]);
  52.             cache[calcCachePos(indexes, strings)] = result;
  53.             return result;
  54.         }
  55.         else
  56.         {
  57.             String[] subStrings = new String[strings.length];
  58.             for (int i = 0; i < strings.length; i++)
  59.             {
  60.                 if (indexes[i] <= 0)
  61.                     subStrings[i] = "";
  62.                 else
  63.                 {
  64.                     int[] newIndexes = new int[indexes.length];
  65.                     for (int j = 0; j < indexes.length; j++)
  66.                         newIndexes[j] = indexes[j];
  67.                     newIndexes[i]--;
  68.                     int cachePos = calcCachePos(newIndexes, strings);
  69.                     if (cache[cachePos] == null)
  70.                         subStrings[i] = lcsBack(strings, newIndexes, cache);
  71.                     else
  72.                         subStrings[i] = cache[cachePos];
  73.                 }
  74.             }
  75.             String longestString = "";
  76.             int longestlength = 0;
  77.             for (int i = 0; i < subStrings.length; i++)
  78.             {
  79.                 if (subStrings[i].length() > longestlength)
  80.                 {
  81.                     longestString = subStrings[i];
  82.                     longestlength = longestString.length();
  83.                 }
  84.             }
  85.             cache[calcCachePos(indexes, strings)] = longestString;
  86.             return longestString;
  87.         }
  88.     }
  89.  
  90.     public static int calcCachePos(int[] indexes, String[] strings)
  91.     {
  92.         int factor = 1;
  93.         int pos = 0;
  94.         for (int i = 0; i < indexes.length; i++)
  95.         {
  96.             pos += indexes[i] * factor;
  97.             factor *= strings[i].length();
  98.         }
  99.         return pos;
  100.     }
  101.  
  102.     public static void main(String[] args) throws IOException
  103.     {
  104.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  105.         System.out.println("Longest Common Subsequence Algorithm Test");
  106.         System.out.println("Enter string 1");
  107.         String str1 = br.readLine();
  108.         System.out.println("Enter string 2");
  109.         String str2 = br.readLine();
  110.         System.out.println("Enter string 3");
  111.         String str3 = br.readLine();
  112.         System.out.println("Enter string 4");
  113.         String str4 = br.readLine();
  114.         String[] str = new String[] { str1, str2, str3, str4 };
  115.         System.out.println(lcs(str));
  116.     }
  117. }

Output:

$ javac LongestCommonSubsequencetoSequences.java
$ java LongestCommonSubsequencetoSequences
 
Longest Common Subsequence Algorithm Test
Enter string 1
Longest Common Subsequence
Enter string 2
Common Subsequence
Enter string 3
Shortest Common Subsequence
Enter string 4
Is it Common Subsequence
 
Common Subsequence
 
Longest Common Subsequence Algorithm Test
Enter string 1
Sanfoundry
Enter string 2
LearningCenter
Enter string 3
CLinuxJava
Enter string 4
ProgrammingSkills
 
a

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.