# Java Program for Longest Common Subsequence (LCS) Problem

The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences).

```import java.io.*;
import java.util.*;
import java.lang.*;

class LCS1 {
public static void main(String args[]) throws IOException {
int i, j, m, n, c[][], lcs[], ct = 1;
String x, y;
char b[][];
c = new int[50][50];
lcs = new int[10];
DataInputStream br = new DataInputStream(System.in);
System.out.print("Enter the Total length of Sequence 1:");
System.out.println("Enter the Sequence1:");
System.out.print("Enter the Total length of Sequence 2:");
System.out.print("Enter the Sequence2:");
b = new char[m + 1][n + 1];
for (i = 0; i <= m; i++)
c[i][0] = 0;
for (j = 0; j <= n; j++)
c[0][j] = 0;
System.out.println(" Table ");
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
if (i == 0 || j == 0) {
System.out.print(c[i][j]);
continue;
}
if ((x.charAt(i) == y.charAt(j))) {
b[i][j] = '\\';
System.out.print(b[i][j]);
c[i][j] = c[i - 1][j - 1] + 1;
System.out.print(c[i][j]);
} else {
if (c[i - 1][j] >= c[i][j - 1]) {
b[i][j] = '|';
System.out.print(b[i][j]);
c[i][j] = c[i - 1][j];
System.out.print(c[i][j]);
} else {
b[i][j] = '-';
System.out.print(b[i][j]);
c[i][j] = c[i][j - 1];
System.out.print(c[i][j]);
}
}
}
System.out.println();
}
i = m - 1;
j = n - 1;
System.out.println(i);
System.out.println(j);
System.out.print("Longest Common Subsequence is :");
while (i > 0 || j > 0) {
if (b[i][j] == '\\') {
lcs[ct] = i;
ct++;
i -= 1;
j -= 1;
} else {
if (b[i][j] == '|') {
i -= 1;
j = j;
} else {
i = i;
j -= 1;
}
}
}
for (i = ct; i > 0; i--) {
j = lcs[i];
System.out.print(x.charAt(j));
}

}
}

/*
OUTPUT
Enter the Total length of Sequence 1:9
Enter the Sequence1: president
Enter the Total length of Sequence 2:10
Enter the Sequence2: providence

Table

0     0     0     0     0     0     0     0     0     0     0

0     \1    -1    -1    -1    -1    -1    -1    -1    -1    -1

0     |1    \2    -2    -2    -2    -2    -2    -2    -2    -2

0     |1    |2    |2    |2    |2    |2    \3    -3    -3    \3

0     |1    |2    |2    |2    |2    |2    |3    |3    |3    |3

0     |1    |2    |2    |2    \3    -3    |3    |3    |3    |3

0     |1    |2    |2    |2    |3    \4    -4    -4    -4    -4

0     |1    |2    |2    |2    |3    |4    \5    -5    -5    \5

0     |1    |2    |2    |2    |3    |4    |5    \6    -6    -6

0     |1    |2    |2    |2    |3    |4    |5    |6    |6    |6

Longest Common Subsequence is :priden
*/
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.