From 61ffe2a9e5fd066dae82a32185bbfe821696bd8a Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Tue, 25 Dec 2018 16:42:27 -0600
Subject: Longest subsequence done! (3 seqs)

The only tricky part was to create and populate the 3-d list. The
instructions here was helpful:
https://www.ict.social/python/basics/multidimensional-lists-in-python---
 AlgoDesignAndTechniqueEdxPython/sources/lcs3.py | 44 +++++++++++++++++++++++++
 1 file changed, 44 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxPython/sources/lcs3.py

(limited to 'AlgoDesignAndTechniqueEdxPython/sources/lcs3.py')

diff --git a/AlgoDesignAndTechniqueEdxPython/sources/lcs3.py b/AlgoDesignAndTechniqueEdxPython/sources/lcs3.py
new file mode 100644
index 0000000..4de6a44
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/lcs3.py
@@ -0,0 +1,44 @@
+#Uses python3
+
+import sys
+def getLCS3(a, b, c):
+    l = len(c)
+    m = len(b)
+    n = len(a)
+# https://www.ict.social/python/basics/multidimensional-lists-in-python
+# The link above provides good tutorial for creating the 3-d list.
+    D = []
+    for _ in range(n + 1):
+        x = []
+        for _ in range(m + 1):
+            y = []
+            for _ in range(l + 1):
+                y.append(0)
+            x.append(y)
+        D.append(x)
+    
+    for k in range(1, l + 1):
+        for j in range(1, m + 1):
+            for i in range(1, n + 1):
+                if a[i - 1] == b[j - 1] == c[k - 1]:
+                    D[i][j][k] = D[i - 1][j - 1][k - 1] + 1
+                else:
+                    D[i][j][k] = max(D[i - 1][j][k], D[i][j - 1][k], D[i][j][k - 1])
+
+    return D[n][m][l]
+
+if __name__ == '__main__':
+    input = sys.stdin.read()
+    data = list(map(int, input.split()))
+    an = data[0]
+    data = data[1:]
+    a = data[:an]
+    data = data[an:]
+    bn = data[0]
+    data = data[1:]
+    b = data[:bn]
+    data = data[bn:]
+    cn = data[0]
+    data = data[1:]
+    c = data[:cn]
+    print(getLCS3(a, b, c))
\ No newline at end of file
-- 
cgit v1.2.3