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.

```
 
```
```
package com.sanfoundry.setandstring;
```
```
 
```
```
import java.io.BufferedReader;
```
```
import java.io.InputStreamReader;
```
```
import java.io.IOException;
```
```
 
```

public class LongestCommonSubsequencetoSequences

```
{
```

    public static String lcs(String[] strings)

```
    {
```
```
        if (strings.length == 0)
```
```
            return "";
```
```
        if (strings.length == 1)
```
```
            return strings[0];
```
```
        int max = -1;
```
```
        int cacheSize = 1;
```

        for (int i = 0; i < strings.length; i++)

```
        {
```

            cacheSize *= strings[i].length();

            if (strings[i].length() > max)

                max = strings[i].length();

```
        }
```

        String[] cache = new String[cacheSize];

        int[] indexes = new int[strings.length];

        for (int i = 0; i < indexes.length; i++)

            indexes[i] = strings[i].length() - 1;

        return lcsBack(strings, indexes, cache);

```
    }
```
```
 
```

    public static String lcsBack(String[] strings, int[] indexes, String[] cache)

```
    {
```

        for (int i = 0; i < indexes.length; i++)

```
            if (indexes[i] == -1)
```
```
                return "";
```
```
        boolean match = true;
```

        for (int i = 1; i < indexes.length; i++)

```
        {
```

            if (strings[0].charAt(indexes[0]) != strings[i].charAt(indexes[i]))

```
            {
```
```
                match = false;
```
```
                break;
```
```
            }
```
```
        }
```
```
        if (match)
```
```
        {
```

            int[] newIndexes = new int[indexes.length];

            for (int i = 0; i < indexes.length; i++)

                newIndexes[i] = indexes[i] - 1;

            String result = lcsBack(strings, newIndexes, cache)

                    + strings[0].charAt(indexes[0]);

            cache[calcCachePos(indexes, strings)] = result;

```
            return result;
```
```
        }
```
```
        else
```
```
        {
```

            String[] subStrings = new String[strings.length];

            for (int i = 0; i < strings.length; i++)

```
            {
```
```
                if (indexes[i] <= 0)
```
```
                    subStrings[i] = "";
```
```
                else
```
```
                {
```

                    int[] newIndexes = new int[indexes.length];

                    for (int j = 0; j < indexes.length; j++)

                        newIndexes[j] = indexes[j];

```
                    newIndexes[i]--;
```

                    int cachePos = calcCachePos(newIndexes, strings);

                    if (cache[cachePos] == null)

                        subStrings[i] = lcsBack(strings, newIndexes, cache);

```
                    else
```

                        subStrings[i] = cache[cachePos];

```
                }
```
```
            }
```
```
            String longestString = "";
```
```
            int longestlength = 0;
```

            for (int i = 0; i < subStrings.length; i++)

```
            {
```

                if (subStrings[i].length() > longestlength)

```
                {
```

                    longestString = subStrings[i];

                    longestlength = longestString.length();

```
                }
```
```
            }
```

            cache[calcCachePos(indexes, strings)] = longestString;

```
            return longestString;
```
```
        }
```
```
    }
```
```
 
```

    public static int calcCachePos(int[] indexes, String[] strings)

```
    {
```
```
        int factor = 1;
```
```
        int pos = 0;
```

        for (int i = 0; i < indexes.length; i++)

```
        {
```
```
            pos += indexes[i] * factor;
```

            factor *= strings[i].length();

```
        }
```
```
        return pos;
```
```
    }
```
```
 
```

    public static void main(String[] args) throws IOException

```
    {
```

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        System.out.println("Longest Common Subsequence Algorithm Test");

        System.out.println("Enter string 1");

```
        String str1 = br.readLine();
```

        System.out.println("Enter string 2");

```
        String str2 = br.readLine();
```

        System.out.println("Enter string 3");

```
        String str3 = br.readLine();
```

        System.out.println("Enter string 4");

```
        String str4 = br.readLine();
```

        String[] str = new String[] { str1, str2, str3, str4 };

```
        System.out.println(lcs(str));
```
```
    }
```
```
}
```

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.

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

« Prev - Java Program to Show the Duality Transformation of Line and Point

» Next - Java Program to Implement Affine Cipher

Related Posts:

Recommended Articles: