AlgorithmsPractice/LCS.java at master · jigsaw004/AlgorithmsPractice · GitHub

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//http://www.practice.geeksforgeeks.org/problem-page.php?pid=152
importjava.util.*;
importjava.lang.*;
importjava.io.*;

classGFG {
publicstaticvoidmain (String[] args) throwsIOException{
Reader.init(System.in);
intT = Reader.nextInt();
while(T-->0){
intA = Reader.nextInt();
intB = Reader.nextInt();
Stringstr1 = Reader.next();
Stringstr2 = Reader.next();
System.out.println(LCS(str1, str2, A, B));
 }
	}
publicstaticintLCS(Strings1, Strings2, intA, intB){
if(s1 == null || s1.isEmpty() || s2 == null || s2.isEmpty()) return0;
int[][] memo = newint[A][B];
memo[0][0] = s1.charAt(0) == s2.charAt(0) ? 1 : 0;
for(inti = 0; i < A; i++){
for(intj = 0; j < B; j++){
if(s1.charAt(i) == s2.charAt(j)){
if(i > 0 && j > 0){
memo[i][j] = 1+memo[i-1][j-1];
 }
elseif(i == 0 && j > 0){
memo[i][j] = 1;
 }
elseif(i > 0 && j == 0){
memo[i][j] = 1;
 }
 }
else{
if(i > 0 && j > 0){
memo[i][j] = max(memo[i-1][j], memo[i][j-1]);
 }
elseif(i == 0 && j > 0){
memo[i][j] = memo[i][j-1];
 }
elseif(i > 0 && j == 0){
memo[i][j] = memo[i-1][j];
 }
 }
 }
 }
returnmemo[A-1][B-1];
	}
publicstaticintmax(inta, intb){
returna > b ? a : b;
	}
}
classReader {
staticBufferedReaderreader;
staticStringTokenizertokenizer;

/** call this method to initialize reader for InputStream */
staticvoidinit(InputStreaminput) {
reader = newBufferedReader(
newInputStreamReader(input) );
tokenizer = newStringTokenizer("");
 }

/** get next word */
staticStringnext() throwsIOException {
while ( ! tokenizer.hasMoreTokens() ) {
//TODO add check for eof if necessary
tokenizer = newStringTokenizer(
reader.readLine() );
 }
returntokenizer.nextToken();
 }

staticintnextInt() throwsIOException {
returnInteger.parseInt( next() );
 }

staticlongnextLong() throwsIOException{
returnLong.parseLong( next() );
 }

staticdoublenextDouble() throwsIOException {
returnDouble.parseDouble( next() );
 }
}
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//http://www.practice.geeksforgeeks.org/problem-page.php?pid=152
importjava.util.*;
importjava.lang.*;
importjava.io.*;

classGFG {
publicstaticvoidmain (String[] args) throwsIOException{
Reader.init(System.in);
intT = Reader.nextInt();
while(T-->0){
intA = Reader.nextInt();
intB = Reader.nextInt();
Stringstr1 = Reader.next();
Stringstr2 = Reader.next();
System.out.println(LCS(str1, str2, A, B));
 }
	}
publicstaticintLCS(Strings1, Strings2, intA, intB){
if(s1 == null || s1.isEmpty() || s2 == null || s2.isEmpty()) return0;
int[][] memo = newint[A][B];
memo[0][0] = s1.charAt(0) == s2.charAt(0) ? 1 : 0;
for(inti = 0; i < A; i++){
for(intj = 0; j < B; j++){
if(s1.charAt(i) == s2.charAt(j)){
if(i > 0 && j > 0){
memo[i][j] = 1+memo[i-1][j-1];
 }
elseif(i == 0 && j > 0){
memo[i][j] = 1;
 }
elseif(i > 0 && j == 0){
memo[i][j] = 1;
 }
 }
else{
if(i > 0 && j > 0){
memo[i][j] = max(memo[i-1][j], memo[i][j-1]);
 }
elseif(i == 0 && j > 0){
memo[i][j] = memo[i][j-1];
 }
elseif(i > 0 && j == 0){
memo[i][j] = memo[i-1][j];
 }
 }
 }
 }
returnmemo[A-1][B-1];
	}
publicstaticintmax(inta, intb){
returna > b ? a : b;
	}
}
classReader {
staticBufferedReaderreader;
staticStringTokenizertokenizer;

/** call this method to initialize reader for InputStream */
staticvoidinit(InputStreaminput) {
reader = newBufferedReader(
newInputStreamReader(input) );
tokenizer = newStringTokenizer("");
 }

/** get next word */
staticStringnext() throwsIOException {
while ( ! tokenizer.hasMoreTokens() ) {
//TODO add check for eof if necessary
tokenizer = newStringTokenizer(
reader.readLine() );
 }
returntokenizer.nextToken();
 }

staticintnextInt() throwsIOException {
returnInteger.parseInt( next() );
 }

staticlongnextLong() throwsIOException{
returnLong.parseLong( next() );
 }

staticdoublenextDouble() throwsIOException {
returnDouble.parseDouble( next() );
 }
}