FilesExpand file tree

 master

/

LCS.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

33 lines (30 loc) · 693 Bytes

 master

/

LCS.java

Copy path

Top

File metadata and controls

• Code
• Blame

33 lines (30 loc) · 693 Bytes

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

public class LCS {

public int max ( int a, int b) {

return (a>b) ? a: b;

}

public int lcs (String a, String b) {

int m = a.length();

int n = b.length();

int[][] l = new int[m + 1][n + 1];

for ( int i = 0; i <= m; i++ ) {

for (int j = 0; j <= n; j++ ) {

if ( i == 0 || j == 0 ) {

l[i][j] = 0;

}

else if ( a.charAt(i -1) == b.charAt(j-1)) {

l[i][j] = l[i-1][j-1] + 1;

}

else {

l[i][j] = max(l[i-1][j], l[i][j-1]);

}

}

}

return l[m][n];

}

public static void main( String[] argvs ) {

String x = "AGGTAB";

String y = "GXTXAYB";

LCS lcs = new LCS();

System.out.println( "Length of LCS is " + lcs.lcs( x, y ) );

}

}