# DP-Longest common subsequence

## Introduction

### Definition
---
**1. subsequence**

\begin{align}
&\text{Given a sequence }
X = \langle x_1,x_2,...,x_m \rangle \text{ ,}\\
&\text{another sequence }
Z = \langle z_1,z_2,...,z_k \rangle
\text{ is a }
\color{blue}{\text{subsequence}}
\text{ of X} \\
&\text{if there exists a strictly increasing sequence }
\langle i_1,i_2,...,i_k \rangle
\text{ of indices of } X \\
&\text{such that } \forall j = 1,2,...,k \quad\exists \text{ } {x_i}_j = z_j
\end{align}

:::success
:bulb: exmaple
  Z = $\langle B,C,D,B\rangle$
  X = $\langle A,B,C,D,A,B \rangle$ with corresponding index sequence $\langle 2,3,5,7 \rangle$
:::

**2. common subsequence**

\begin{align}
&\text{Given two sequences }X\text{ and }Y,
\text{ we say that a sequence }\\
&Z\text{ is a }
\color{blue}{\text{common subsequence}}
\text{ of } X \text{ and }Y \\
&\text{if } Z \text{ is a subsequence of both } X \text{ and } Y
\end{align}

**3. prefix**

\begin{align}
&\text{the } i \text{ th } \color{blue}{\text{prefix}} \text{ of } X,\text{ for } i = 0,1,...,m, \text{as } X_i = \langle x_1,x_2,...,x_i \rangle
\end{align}

:::success
:bulb: exmaple
   $\text{if } X = \langle A,B,C,B,D,A,B \rangle \text{ then } X_4 = \langle A,B,C,B\rangle$
:::

### Theorem (Optimal substructure of an LCS)
---

$Let \ X = \langle x_1, \ x_2, \ ..., \ x_m \rangle \
and \ Y = \langle y_1, \ y_2, \ ..., \ y_n \rangle \ be \ sequences,$
$Let \ Z = \langle z_1, \ z_2, \ ... , \ z_k \rangle \ be \ any \ LCS \ of \ X \ and \ Y .$

$1. \ if \ x_m = y_n, \ then \ z_k = x_m = y_n \ and \ Z_{k-1} \ is \ an \ LCS \ of \ X_{m-1} \ and \ Y_{n-1}$

$2. \ if \ x_m \neq y_n \ and \ z_k \neq x_m, \ then \ Z \ is \ an \ LCS \ of X_{m-1} \ and \ Y$

$3. \ if \ x_m \neq y_n \ and \ z_k \neq y_n, \ then \ Z \ is \ an \ LCS \ of \ X \ and \ Y_{n-1}$

> 這段主要在敘述X和Y序列最後一個字相等關係，決定LCS是由哪些更小的子序列LCS組成

$Proof$

$1. \ Given \ x_m = y_n , \ if \ z_k \neq x_m$
$\ \implies \ we \ could \ append \ x_m = y_n \ to \ Z$
$\ \implies \ obtain \ a \ new \ common \ subsequence \ Z_{new} \ with \ length \ k+1$
$\ \implies \ Contradiction\ !!$
$\therefore \ x_m = y_n = z_k$

$\ Suppose \ W \ is \ a \ common \ subsequence \ of \ X_{m-1} \ and \ Y_{n-1}$
$\ with \ a \ length \ greater \ than \ k$
$\ \implies we \ can \ append \ x_m = y_n \ to \ W$
$\ \implies the \ length \ of \ W \ is \ greater \ than \ k$
$\ \implies \ Contradiction \ !!$
$\ \therefore we \ can \ alse \ proof \ Z_{k-1} \ is \ an \ LCS \ of \ X_{m-1} \ and \ Y_{n-1}$

$2. \ Given \ x_m \neq y_n, \ and \ z_k \neq x_m,$
$\ \ Suppose \ W \ is \ a \ common \ subsequence \ of \ X_{m-1} \ and \ Y \ with\ legth \ greater \ than \ k$
$\ \implies W \ would \ alse \ be \ a \ common \ subsequence \ of \ X_m \ and \ Y$
$\ \implies Z \ is \ not \ an \ LCS \ of \ X \ and \ Y$
$\ \implies \ Contradiction\ !!$

$3. \ The \ proof \ is \ symmetric \ to (2)$

:::success
:bulb: if the last char of the sequence $\not\in Z$ we can ignore that char to reduce problem
:::

:::success
:bulb: Note
we can use those property to solve problem

$if \ x_m = y_n$
$\ \implies \ add \ the \ character \ to \ LCS \ answer \ and \ find \ LCS \ of \ X_{m-1} \ and \ Y_{n-1}$
$if \ x_m \neq y_n$
$\ \implies \ solve \ two \ subproblem: \ LCS \ of \ X_{m-1} \ and \ Y_n \ , \ LCS \ of \ X_{m} \ and \ Y_{n-1}$

:::warning
:warning: The LCS problem has the overlapping-subproblems property
$\because$ LCS of $X_{m-1}$ $Y_{n}$ and $X_m$ $Y_{n-1}$
    share subproblem of LCS of $X_{m-1}$ and $Y_{n-1}$
:::

### Recurrence
---
$\text{Let c [i, j] to be the length of an LCS of the sequence }X_i \text{ and }Y_j$

\begin{align}
&c[i, j] =
\begin{cases}
0 &\text{if i = 0 or j = 0}\\
c\ [\ i - 1, \ j - 1] + 1 &\text{if i, j > 0 and }x_i = y_j\\
max\{\ c \ [i, \ j -1], \ c[i - 1, \ j], \ j\ \} &\text{if i, j > 0 and }x_i \neq y_j
\end{cases}
\end{align}

:::warning
Step 1: Calculate LCS length of the subproblem (Row major) (Bottom-Up)
Step 2: Use the table to find the answer
Step 3: Print answer by DFS
:::
### Implement
---

#include <iostream>
#include <string>
using namespace std;

enum Dir {LEFT_TOP, LEFT, TOP};
string x, y;

void sovle(int** c, Dir **b, int m, int n) {
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (x[i-1] == y[j-1]) {
                b[i][j] = LEFT_TOP;
                c[i][j] = c[i-1][j-1] + 1;
            }
            else if (c[i-1][j] >= c[i][j-1]) {
                b[i][j] = TOP;
                c[i][j] = c[i-1][j];
            }
            else {
                b[i][j] = LEFT;
                c[i][j] = c[i][j-1];
            }
        }
    }
}

void print_ans(Dir** b, int m, int n) {
    if (!m || !n)
        return;
    switch (b[m][n]) {
        case LEFT_TOP:
            print_ans(b, m-1, n-1);
            cout << x[m-1] << " ";
            break;
        case LEFT: 
            print_ans(b, m, n-1);
            break;
        case TOP:
            print_ans(b, m-1, n);
            break;
    }
}

int main() {
    int m, n;
    char tmp;

    cin >> m >> n;

    x.clear();
    y.clear();
    for (int i = 0; i < m; i++) {
        cin >> tmp;
        x += tmp;
    }

    for (int i = 0; i < n; i++) {
        cin >> tmp;
        y += tmp;
    }

    int** lcs_len = new int*[m+1];
    Dir** lcs_dir = new Dir*[m+1];
    for (int i = 0; i <= m; i++) {
        lcs_len[i] = new int[n+1];
        lcs_dir[i] = new Dir[n+1];
        for (int j = 0; j <= n; j++) {
            lcs_len[i][j] = 0;
        }
    }

    sovle(lcs_len, lcs_dir, m, n);
    print_ans(lcs_dir, m, n);
    cout << endl;
}

### Reference
---
* Introduction to algorithms 4th edition

>[name=Sky]
###### tags: `Algorithm`