diff options
Diffstat (limited to 'AlgoDesignAndTechniqueEdxJava/sources')
-rw-r--r-- | AlgoDesignAndTechniqueEdxJava/sources/LCS2.java | 56 |
1 files changed, 55 insertions, 1 deletions
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java b/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java index d214eff..e2a882c 100644 --- a/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java +++ b/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java @@ -1,4 +1,6 @@ +import java.util.Arrays; import java.util.Scanner; +//import java.util.concurrent.ThreadLocalRandom; public class LCS2 { @@ -16,7 +18,33 @@ public class LCS2 { b[i] = scanner.nextInt(); } - System.out.println(lcs2(a, b)); + System.out.println(third_lcs2(a, b)); +// System.out.println(alt_lcs2(a, b, n, m)); + +// while (true) { +//// int n = ThreadLocalRandom.current().nextInt(1, 101); +//// int m = ThreadLocalRandom.current().nextInt(1, 101); +// int n = ThreadLocalRandom.current().nextInt(1, 20); +// int m = ThreadLocalRandom.current().nextInt(1, 20); +// int[] a = new int[n]; +// int[] b = new int[m]; +// for (int i = 0; i < a.length; i++) { +// a[i] = ThreadLocalRandom.current().nextInt(-999999999, 1000000000); +// } +// for (int i = 0; i < b.length; i++) { +// b[i] = ThreadLocalRandom.current().nextInt(-999999999, 1000000000); +// } +// int r1 = lcs2(a, b); +// int r2 = alt_lcs2(a, b, n, m); +// if (r1 == r2) +// System.out.println("ok"); +// else { +// System.out.println(Arrays.toString(a)); +// System.out.println(Arrays.toString(b)); +// System.out.println("Wrong answer " + r1 + " " + r2); +// break; +// } +// } } public static int[][] editDistance(int[] A, int[] B) { @@ -66,4 +94,30 @@ public class LCS2 { return lcs2(i - 1, j - 1, D); } + public static int alt_lcs2(int[] a, int[] b, int i, int j) { + if (i == 0 || j == 0) + return 0; + if (a[i - 1] == b[j - 1]) + return 1 + alt_lcs2(a, b, i - 1, j - 1); + else + return Math.max(alt_lcs2(a, b, i, j - 1), alt_lcs2(a, b, i - 1, j)); + } + + public static int third_lcs2(int[] a, int[] b) { + int m = b.length; + int n = a.length; + int[][] D = new int[n + 1][m + 1]; + for (int j = 1; j < m + 1; j++) { + for (int i = 1; i < n + 1; i++) { + if (a[i - 1] == b[j - 1]) { + D[i][j] = D[i - 1][j - 1] + 1; + } else { + D[i][j] = Math.max(D[i - 1][j], D[i][j - 1]); + } + } + } + + return D[n][m]; + } + } |