summaryrefslogtreecommitdiff
path: root/AlgoDesignAndTechniqueEdxPython/sources/lcs2.py
diff options
context:
space:
mode:
Diffstat (limited to 'AlgoDesignAndTechniqueEdxPython/sources/lcs2.py')
-rw-r--r--AlgoDesignAndTechniqueEdxPython/sources/lcs2.py35
1 files changed, 35 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/lcs2.py b/AlgoDesignAndTechniqueEdxPython/sources/lcs2.py
new file mode 100644
index 0000000..76f73fd
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/lcs2.py
@@ -0,0 +1,35 @@
+# Uses python3
+
+import sys
+
+
+def getLCS2Length(a, b):
+ m = len(b)
+ n = len(a)
+
+ D = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
+
+ for j in range(1, m + 1):
+ for i in range(1, n + 1):
+ if a[i - 1] == b[j - 1]:
+ D[i][j] = D[i - 1][j - 1] + 1
+ else:
+ D[i][j] = max(D[i - 1][j], D[i][j - 1])
+
+ return D[n][m]
+
+
+if __name__ == '__main__':
+ input = sys.stdin.read()
+ data = list(map(int, input.split()))
+
+ n = data[0]
+ data = data[1:]
+ a = data[:n]
+
+ data = data[n:]
+ m = data[0]
+ data = data[1:]
+ b = data[:m]
+
+ print(getLCS2Length(a, b))