python: Longest common subsequence (LCS) algorithm

lcs.py

from functools import lru_cache


@lru_cache(maxsize=2**20)
def LCS(a, b):
    """ Longest common subsequence """
    if len(a) == 0 or len(b) == 0:
        return 0

    res = max(
        LCS(a[:-1], b),
        LCS(a, b[:-1])
    )

    if a[-1] == b[-1]:
        res = max(res, LCS(a[:-1], b[:-1]) + 1)

    return res