Source code for tryalgo.longest_common_subsequence

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Longest increasing subsequence
jill-jênn vie et christoph dürr - 2014-2019
"""
# pylint: disable=bad-whitespace


# snip{
[docs]def longest_common_subsequence(x, y): """Longest common subsequence Dynamic programming :param x: :param y: x, y are lists or strings :returns: longest common subsequence in form of a string :complexity: `O(|x|*|y|)` """ n = len(x) m = len(y) # -- compute optimal length A = [[0 for j in range(m + 1)] for i in range(n + 1)] for i in range(n): for j in range(m): if x[i] == y[j]: A[i + 1][j + 1] = A[i][j] + 1 else: A[i + 1][j + 1] = max(A[i][j + 1], A[i + 1][j]) # -- extract solution in reverse order sol = [] i, j = n, m while A[i][j] > 0: if A[i][j] == A[i - 1][j]: i -= 1 elif A[i][j] == A[i][j - 1]: j -= 1 else: i -= 1 j -= 1 sol.append(x[i]) return ''.join(sol[::-1]) # reverse the list to obtain the solution
# snip}