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:");
m = Integer.parseInt(br.readLine());
System.out.println("Enter the Sequence1:");
x = br.readLine();
System.out.print("Enter the Total length of Sequence 2:");
n = Integer.parseInt(br.readLine());
System.out.print("Enter the Sequence2:");
y = br.readLine();
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
*/