Longest Common Subsequence (最長共通部分列)
(Sequence/Longest_Common_Subsequence.py)

• View this file on GitHub
• Last update: 2022-11-26 03:55:08+09:00

Outline

2つの列 $S,T$ に対する最長共通部分や, その長さを求める.

Theory

$\mathcal{A}$ をアルファベットとする. $S \in W(\mathcal{A})$ に対して, 以下を満たすような正の整数列 $\rho$ が存在するとき, $T \in W(\mathcal{A})$ は $S$ の部分列であるという.

• $\rho$ は長さ $\lvert T \rvert$ の列.
• $1 \leq \rho(1) \lt \rho(2) \lt \dots \lt \rho(\lvert T \rvert) \leq \lvert S \rvert$.
• $i=1,2, \dots, \lvert T \rvert$ に対して, $S_{\rho(i)}=T_i$ が成り立つ.

2つの列 $S,T \in W(\mathcal{A})$ に対して, $S,T$ 両方の部分列であるような列のことを $S,T$ の共通部分列という.

$S,T$ の共通部分列のうち, 長さが最大であるようなものを最長共通部分列という (存在はするが, 一意とは限らない).

$S,T$ の最長共通部分列の長さは以下のようにして動的計画法で求めることができる.

${\rm DP}[i,j]$ を $S[1:i], T[1:j]$ の最長共通部分列の長さとする. 自明なケースとして,

\[{\rm DP}[0,j]=0 \quad (0 \leq j \leq \lvert T \rvert), \quad {\rm DP}[i,0]=0 \quad (0 \leq i \leq \lvert S \rvert)\]

である.

また, 更新式は次のようになる.

\[{\rm DP}[i,j]=\begin{cases} {\rm DP}[i-1, j-1]+1 & (S_i=T_j) \\ \max ({\rm DP}[i-1,j], {\rm DP}[i, j-1]) & (S_i \neq T_j) \end{cases}\]

この動的計画法によって, ${\rm DP}[\lvert S \rvert, \lvert T \rvert]$ が $S,T$ の最長共通部分列の長さになる.

Code

#最長部分列
def Longest_Common_Subsequence(S, T, example=False):
    """ 列 S,T における最長部分列の長さを求める.

    example: True であるとき, LCS を満たす例を1つ返す.
    """

    M=len(S); N=len(T)
    DP=[[0]*(N+1) for _ in range(M+1)]

    for i in range(1,M+1):
        D=DP[i]
        E=DP[i-1]
        for j in range(1,N+1):
            if S[i-1]==T[j-1]:
                D[j]=E[j-1]+1
            else:
                if E[j]>=D[j-1]:
                    D[j]=E[j]
                else:
                    D[j]=D[j-1]

    if not example:
        return D[-1]

    X=[]
    I,J=M,N
    D=DP[I]; E=DP[I-1]
    while D[J]:
        if S[I-1]==T[J-1]:
            X.append(S[I-1])
            I-=1; J-=1
            D=DP[I]
            E=DP[I-1]
        else:
            if D[J]==D[J-1]:
                J-=1
            else:
                I-=1
                D=DP[I]
                E=DP[I-1]

    return DP[-1][-1], X[::-1]

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/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.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page