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
| package bbm.dp;
import java.util.ArrayList;
public class LongestCommonSubSequence {
public ArrayList<Character> lcsLength(char[] x, char[] y) { char[][] path = new char[x.length + 1][y.length + 1]; int[][] length = new int[x.length + 1][y.length + 1]; for (int i = 0; i < x.length; i++) { for (int j = 0; j < y.length; j++) { if (x[i] == y[j]) { length[i + 1][j + 1] = length[i][j] + 1; path[i + 1][j + 1] = '↖'; } else if (length[i][j + 1] > length[i + 1][j]) { length[i + 1][j + 1] = length[i][j + 1]; path[i + 1][j + 1] = '↑'; } else { length[i + 1][j + 1] = length[i + 1][j]; path[i + 1][j + 1] = '←'; } } } System.out.print(' '); System.out.print(' '); for (char c : y) { System.out.print(c); System.out.print(' '); System.out.print(' '); } System.out.println(); for (int i = 1; i < path.length; i++) { System.out.print(x[i - 1]); System.out.print(' '); for (int j = 1; j < path[i].length; j++) { System.out.print(path[i][j]); System.out.print(length[i][j]); System.out.print(' '); } System.out.println(); } ArrayList<Character> result = new ArrayList<>(); getPath(result, x, path, x.length, y.length); return result; }
private void getPath(ArrayList<Character> result, char[] x, char[][] path, int i, int j) { if (i == 0 || j == 0) { return; } if (path[i][j] == '↖') { getPath(result, x, path, i - 1, j - 1); result.add(x[i - 1]); } else if (path[i][j] == '↑') { getPath(result, x, path, i - 1, j); } else { getPath(result, x, path, i, j - 1); } }
public static void main(String[] args) { ArrayList<Character> result = new LongestCommonSubSequence() .lcsLength(new char[] {'a', 'b', 'c', 'b', 'd', 'a', 'b'}, new char[] {'b', 'd', 'c', 'a', 'b', 'a'}); System.out.print("LCS: "); for (char c : result) { System.out.print(c); } System.out.println(); }
}
|