最長共通部分列 (longest common subsequence)
(DP/lcs.py)

• View this file on GitHub
• Last update: 2021-05-06 21:57:26+09:00

概要

最長共通部分列を求めるアルゴリズム。

使い方

lcs(s: str, t: str) -> str
長さ $N$ の文字列 s と長さ $M$ の文字列 t の最長共通部分列を返す。計算量 $O(NM)$

Verified with

• TestCase/AOJ/ALDS1_10_C.test.py

Code

def lcs(s, t):
    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
    for i, chr_s in enumerate(s):
        for j, chr_t in enumerate(t):
            if chr_s == chr_t:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

    res = []
    i, j = len(s), len(t)
    while i > 0 and j > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            res.append(s[i - 1])
            i -= 1
            j -= 1
    return ''.join(reversed(res))

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page