summaryrefslogtreecommitdiff
path: root/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java
diff options
context:
space:
mode:
Diffstat (limited to 'AlgoDesignAndTechniqueEdxJava/sources/LCS2.java')
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/LCS2.java56
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];
+ }
+
}