1 files changed, 24 insertions, 0 deletions
diff --git a/lcs.py b/lcs.py
new file mode 100644
index 0000000..c180241
--- /dev/null
+++ b/lcs.py
@@ -0,0 +1,24 @@
+def LCS(X, Y):
+    m = len(X)
+    n = len(Y)
+    # An (m+1) times (n+1) matrix
+    C = [[0] * (n+1) for i in range(m+1)]
+    for i in range(1, m+1):
+        for j in range(1, n+1):
+            if X[i-1] == Y[j-1]:
+                C[i][j] = C[i-1][j-1] + 1
+            else:
+                C[i][j] = max(C[i][j-1], C[i-1][j])
+    return C
+
+def printDiff(C, X, Y, i, j):
+    if i > 0 and j > 0 and X[i-1] == Y[j-1]:
+        printDiff(C, X, Y, i-1, j-1)
+        print "  " + X[i-1]
+    else:
+        if j > 0 and (i == 0 or C[i][j-1] >= C[i-1][j]):
+            printDiff(C, X, Y, i, j-1)
+            print "+ " + Y[j-1]
+        elif i > 0 and (j == 0 or C[i][j-1] < C[i-1][j]):
+            printDiff(C, X, Y, i-1, j)
+            print "- " + X[i-1]