---
tags: DP
title: LCS
---

:::success

## LCS (Longest Common Subsequence)
- 求 $N$ 個字串的 LCS 是 NP-hard 問題
- 以下講解求兩字串$S_1, S_2$的最常共同子序列的方法s

### 方法一：
- 令$dp[i][j]$為「前$i$個$S_1$的字元組成的字串」跟「前j個S2的字元組成的字串」的LCS
- $dp[i][j]$ =
- $dp[i-1][j-1] + 1$, 如果 $S1[i] = S2[j]$;
- $max(dp[i][j-1], dp[i-1][j])$, 如果 $S1[i] \neq S2[j]$;

- Time Complexity: $O(|S_1|\times|S_2|)$

### 方法二：
- 觀察一下 $S1, S2$ 的LCS分別在兩個字串中的位置，它們都是嚴格遞增序列。
- 舉個栗子：（使用green judge b033 範例二）
[GJ b033](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b033)
S1 = ~A~F~CB~E~C~CFB~D~
S2 = F~F~E~E~C~DDA~FB
- index:
- F(1,0)
- E(4,2)
- C(6,4)
- F(7,8)
- B(8,9)

（很明顯的嚴格遞增序列）

- 作法：把所有字元相同的數對都找出來，然後做LIS
- Time Complexity: $O(m\times logm)$（ $m$ 為數對的數量）
:::
:::info
## 作業
*選個兩題寫ㄅ～*
[PA UVa 10635](http://domen111.github.io/UVa-Easy-Viewer/?10635)
[PB UVa 10949](http://domen111.github.io/UVa-Easy-Viewer/?10949)
[PC UVa 164](http://domen111.github.io/UVa-Easy-Viewer/?164)
[PC UVa 164 中文](http://rubyacm.blogspot.com/2011/05/164-string-computer.html)
[PD ZJ b397](https://zerojudge.tw/ShowProblem?problemid=b397)
:::