summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/LCS2.java69
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/EditDistanceTest.java1
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java35
3 files changed, 105 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java b/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java
new file mode 100644
index 0000000..d214eff
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/LCS2.java
@@ -0,0 +1,69 @@
+import java.util.Scanner;
+
+public class LCS2 {
+
+ public static void main(String[] args) {
+ Scanner scanner = new Scanner(System.in);
+ int n = scanner.nextInt();
+ int[] a = new int[n];
+ for (int i = 0; i < n; i++) {
+ a[i] = scanner.nextInt();
+ }
+
+ int m = scanner.nextInt();
+ int[] b = new int[m];
+ for (int i = 0; i < m; i++) {
+ b[i] = scanner.nextInt();
+ }
+
+ System.out.println(lcs2(a, b));
+ }
+
+ public static int[][] editDistance(int[] A, int[] B) {
+ int m = B.length;
+ int n = A.length;
+ int[][] D = new int[n + 1][m + 1];
+
+ for (int i = 0; i < n + 1; i++) {
+ D[i][0] = i;
+ }
+ for (int j = 0; j < m + 1; j++) {
+ D[0][j] = j;
+ }
+
+ for (int j = 1; j < m + 1; j++) {
+ for (int i = 1; i < n + 1; i++) {
+ int insertion = D[i][j - 1] + 1;
+ int deletion = D[i - 1][j] + 1;
+ int match = D[i - 1][j - 1];
+ int mismatch = D[i - 1][j - 1] + 1;
+ if (A[i - 1] == B[j - 1]) {
+ D[i][j] = Math.min(insertion, Math.min(deletion, match));
+ } else {
+ D[i][j] = Math.min(insertion, Math.min(deletion, mismatch));
+ }
+ }
+ }
+
+ return D;
+ }
+
+ public static int lcs2(int[] a, int[] b) {
+ int D[][] = editDistance(a, b);
+ return lcs2(a.length, b.length, D);
+ }
+
+ private static int lcs2(int i, int j, int[][] D) {
+ if (i == 0 && j == 0)
+ return 0;
+ if (i > 0 && D[i][j] == D[i - 1][j] + 1)
+ return lcs2(i - 1, j, D);
+ if (j > 0 && D[i][j] == D[i][j - 1] + 1)
+ return lcs2(i, j - 1, D);
+ else if (D[i][j] == D[i - 1][j - 1])
+ return 1 + lcs2(i - 1, j - 1, D);
+ else
+ return lcs2(i - 1, j - 1, D);
+ }
+
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/EditDistanceTest.java b/AlgoDesignAndTechniqueEdxJava/tests/EditDistanceTest.java
index 8c10432..e22ed87 100644
--- a/AlgoDesignAndTechniqueEdxJava/tests/EditDistanceTest.java
+++ b/AlgoDesignAndTechniqueEdxJava/tests/EditDistanceTest.java
@@ -7,6 +7,7 @@ class EditDistanceTest {
@Test
void test() {
assertEquals(0, EditDistance.editDistance("ab", "ab"));
+ assertEquals(1, EditDistance.editDistance("a", "x"));
}
@Test
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java b/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java
new file mode 100644
index 0000000..bdfa799
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/LCS2Test.java
@@ -0,0 +1,35 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+class LCS2Test {
+
+ @Test
+ void test() {
+ int[] a = {2, 7, 5};
+ int[] b = {2, 5};
+ assertEquals(2, LCS2.lcs2(a,b));
+ }
+
+ @Test
+ void test1() {
+ int[] a = {7};
+ int[] b = {1, 2, 3, 4};
+ assertEquals(0, LCS2.lcs2(a,b));
+ }
+
+ @Test
+ void test2() {
+ int[] a = {2, 7, 8, 3};
+ int[] b = {5, 2, 8, 7};
+ assertEquals(2, LCS2.lcs2(a,b));
+ }
+
+ @Test
+ void test3() {
+ int[] a = {1, 2, 3, 4, 5, 6, 7};
+ int[] b = {1, 2, 8, 4, 5, 6};
+ assertEquals(5, LCS2.lcs2(a,b));
+ }
+
+}