-
Notifications
You must be signed in to change notification settings - Fork 6
Expand file tree
/
Copy pathLCS.java
More file actions
executable file
·69 lines (54 loc) · 1.79 KB
/
LCS.java
File metadata and controls
executable file
·69 lines (54 loc) · 1.79 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.util.Scanner;
public class LCS {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int i,j;
System.out.print("Enter the first String : ");
String X = in.next();
System.out.print("Enter the Second String : ");
String Y = in.next();
int p = X.length();
int q = Y.length();
int[][] cache = new int[p+1][q+1];
int[][] direction= new int[p+1][q+1];
for (i = 0; i <= p; i++) {
cache[i][0] = 0;
}
for (j = 0; j <= q; j++) {
cache[0][j] = 0;
}
for (i = 1; i <= p; i++) {
for (j = 1; j <= q; j++) {
if (X.charAt(i-1) == Y.charAt(j-1)) {
cache[i][j]=cache[i-1][j-1]+1;
direction[i][j]=1;
}
else if (cache[i-1][j]>=cache[i][j-1]) {
cache[i][j]=cache[i-1][j];
direction[i][j] = 2;
}
else {
cache[i][j]=cache[i][j-1];
direction[i][j]=3;
}
}
}
String lcs = new String();
i=p;
j=q;
while (i!=0 && j!=0) {
if (direction[i][j] ==1) {
lcs =X.charAt(i-1) + lcs;
i = i - 1;
j = j - 1;
}
if (direction[i][j] == 2) {
i = i - 1;
}
if (direction[i][j] == 3) {
j = j - 1;
}
}
System.out.println("The LCS is " + lcs);
}
}