summaryrefslogtreecommitdiff
path: root/AlgoDesignAndTechniqueEdxPython/sources/lcs3.py
diff options
context:
space:
mode:
Diffstat (limited to 'AlgoDesignAndTechniqueEdxPython/sources/lcs3.py')
-rw-r--r--AlgoDesignAndTechniqueEdxPython/sources/lcs3.py44
1 files changed, 44 insertions, 0 deletions
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