[Algorithms] Longest Common Subsequence Problem (LCS) | 최장 공통 부분 순서 문제

Longest Common Subsequence Problem (LCS)

최장 공통 부분 순서 문제

- 두 문자열에 존재하는 가장 긴 공통 부분 순서*를 찾아내는 문제이다.
- 단순히, 전체 문자열에서 부분 문자열을 찾아내는 문제는 문자열 매칭 알고리즘 (URL)을 참고하자.

Example. 공통 부분 순서 (Common Subsequence)

- "bcdb"는 문자열 "abcbdab"의 부분 순서이다.
  ("bcdb"가 문자열 "abcbdab"에 순서대로 나타나기 때문이다.)

- 문자열 "abcbdab"와 문자열 "bdcaba"에 대해,
  문자열 "bca"는 공통 부분 순서 중 하나이다.
  (두 문자열에 "bca"가 순서대로 나타나기 때문이다.)

- 문자열 "abcbdab"와 문자열 "bdcaba"에 대해,
  문자열 "bcba"는 최장 공통 부분 순서이다.

---

Mechanism (원리)

※ 이 문제의 답은 Optimal Substructure를 갖고 있으므로, Dynamic Programming (URL) 기법을 적용해 볼 수 있다.

[Algorithms] Dynamic Programming (DP) | 동적 프로그래밍

- 두 문자열 \(X_m = "x_1x_2 \cdots x_m"\) 와 \(Y_n = "y_1y_2 \cdots y_n"\) 에 존재하는 LCS를 구해보자.
- \(x_m = y_n\) 이면,
  \(X_m\)과 \(Y_n\)의 LCS의 길이는 \(X_{m-1}\)과 \(Y_{n-1}\)의 LCS의 길이보다 1만큼 더 크다.
  즉, \((m, n)\)의 크기 문제의 해가 \((m-1, n-1)\)의 크기 문제의 해를 포함하는 구조이다.
- \(x_m \neq y_n\) 이면,
  \(X_m\)과 \(Y_n\)의 LCS의 길이는
  \(X_m\)과 \(Y_{n-1}\)의 LCS의 길이와 \(X_{m-1}\)과 \(Y_n\)의 LCS의 길이 중 큰 것과 같다.
  즉, \((m, n)\)의 크기 문제의 해가 \((m, n-1)\)의 크기 문제의 해와 \((m-1, n)\)의 크기 문제의 해를 포함하는 구조이다.
- 이와 같은 LCS의 성질을 아래와 같이 정리할 수 있다.

---

Theorem of LCS

\(X_m = "x_1x_2 \cdots x_m"\) 과 \(Y_n = "y_1y_2 \cdots y_n"\)의 LCS의 길이를 \(k\)라 하자. 
LCS는 여러 종류로 존재할 수 있는데, 여러 LCS 중 임의의 하나를 \(Z_k = z_1z_2 \cdots z_k\)라 하자.

1) \(x_m = y_n\) 이면,
   \(z_k = x_m = y_n\) 이고, \(Z_{k-1}\)은 \(X_{m-1}\)과 \(Y_{n-1}\)의 LCS이다.

2) \(x_m \neq y_n\) 이고 \(z_k \neq x_m\) 이면,
   \(Z_k\)는 \(X_{m-1}\)과 \(Y_n\)의 LCS이다.

3) \(x_m \neq y_n\) 이고 \(z_k \neq y_n\) 이면,
   \(Z_k\)는 \(X_m\)과 \(Y_{n-1}\)의 LCS이다.

---

Recursive Formula

\(C_{i, j}\) : 문자열 \(X_i = "x_1x_2 \cdots x_i"\) 와 문자열 \(Y_j = "y_1y_2 \cdots y_j"\)의 LCS의 길이

\(C_{i, j} = 
\begin{cases}
0 \; \; \qquad \qquad \qquad \qquad \qquad \mathrm{(if} \; i = 0 \; \mathrm{or} \; j = 0)\\\\
C_{i-1, j-1} + 1 \, \qquad \qquad \qquad \mathrm{(if} \; i > 0, j > 0, x_i = y_i)\\\\
\mathrm{max}(C_{i-1. j},  C_{i, j-1}) \; \qquad \quad \mathrm{(if} \; i > 0, j > 0, x_i \neq y_i)
\end{cases}\)

---

Implementation

1. Stupid Recursion (\(\Omega(2^n)\))

LCS(m, n)
// 두 문자열 X[1...m]과 Y[1...n]의 LCS의 길이를 리턴한다.
{
    if (m == 0 || n == 0)
        return 0;
    else if (X[m] == Y[n])
        return LCS(m-1, n-1) + 1;
    else
        max(LCS(m-1, n), LCS(m, n-1));
}

Example. Recursion Tree for \(\texttt{LCS(3, 4)}\)

Called \(\texttt{LCS()}\)	\(\texttt{LCS(1, 1)}\)이 호출되는 횟수
LCS(2, 2)	2
LCS(2, 3)	3
LCS(3, 3)	6
LCS(3, 4)	10
LCS(4, 4)	20
LCS(4, 5)	35
LCS(5, 5)	70
LCS(5, 6)	126
LCS(6, 6)	252
LCS(6, 7)	462
LCS(7, 7)	924

2. Dynamic Programming with Loop (\(\Theta(mn)\))

LCS(m, n)
// 두 문자열 X[1...m]과 Y[1...n]의 LCS의 길이를
// C[0...m][0...n]에 저장해가며 계산한다.
{
    for(int i = 0; i < m; i++)
        C[i, 0] = 0;
    for(int j = 0; j < n; j++)
        C[0, j] = 0;
    
    for(int i = 1; i < m; i++)
        for(int j = 1; j < n; j++){
            if(X[i] == Y[i])
                C[i, j] = C[i-1, j-1] + 1;
            else
                C[i, j] = max(C[i-1, j], C[i, j-1]);
                
    return C[m, n];
}

 

---

Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)

Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)