diff options
author | Haidong Ji | 2018-12-25 14:27:29 -0600 |
---|---|---|
committer | Haidong Ji | 2018-12-25 14:27:29 -0600 |
commit | b12193500c0da24a9e7fc5a8523ed2252da88bad (patch) | |
tree | 492708d14c0bba5575452f50d27397361a047536 /AlgoDesignAndTechniqueEdxPython/sources/lcs2.py | |
parent | 33b21ee9aad03b052d14227e023b9697c6ce4a55 (diff) |
Longest subsequence of 2 seqs done!
Not too bad, since I worked it out in Java already.
Diffstat (limited to 'AlgoDesignAndTechniqueEdxPython/sources/lcs2.py')
-rw-r--r-- | AlgoDesignAndTechniqueEdxPython/sources/lcs2.py | 35 |
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)) |