FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
code/Algorithm/LCS.java at master · dwipam/code · GitHub
dwipam
/
code
Public
Notifications
You must be signed in to change notification settings
Fork
6
Star
7
Code
Issues
0
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
code
/
Algorithm
/
LCS.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
executable file
·
69 lines (54 loc) · 1.79 KB
Breadcrumbs
code
/
Algorithm
/
LCS.java
Copy path
File metadata and controls
executable file
·
69 lines (54 loc) · 1.79 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
);
}
}
Back
|
FazBrowse Home
|
New Git URL