1 files changed, 69 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);
+    }
+
+}