Question

Longest Common Subsequence（LCS）

“最长共同子序列”。出现于每一个序列、而且是最长的子序列。可能有许多个。

s1: 2 5 7 9 3 1 2
s2: 3 5 3 2 8

LCS(s1, s2) = 5 3 2

s1: a b c d b c e e a
s2: c a b d e f g a
s3: d c e a

LCS(s1, s2, s3) =  {c e a, d e a}

演算法

求出一群序列的 LCS，是 NP-hard 问题，没有快速的演算法。

简单的方式是穷举法：穷举 s1 的所有子序列，检查 s2...sN 是否都有该子序列。时间複杂度是 O(s1! * (s2 + ... + sN))。

求出两个序列的 LCS，是 P 问题。接下来将介绍各种演算法。

Longest Common Subsequence: Dynamic Programming

分割问题

现在要找出 s1 和 s2 的 LCS。写成 LCS(s1, s2)。

拆解 s1 和 s2 的最后一个元素，叫做 e1 和 e2。

s1 = sub1 + e1
s2 = sub2 + e2

分成四种情况：一、LCS 包含 e1，不含 e2；二、包含 e2，不含 e1；三、不含 e1 e2；四、包含 e1 e2。

第一种情况。e2 毫无用处，想找 LCS 只需要找 sub2。得到结论 LCS(s1, s2) = LCS(s1, sub2)。

第二种情况。LCS(s1, s2) = LCS(sub1, s2)。

第三种情况。LCS(s1, s2) = LCS(sub1, sub2)。

第四种情况。LCS 同时包含 e1 e2，而且 e1 e2 位于尾端。因此 LCS 的最后一个元素一定是 e1（也是 e2），而且 e1 e2 相等！得到结论 LCS(s1, s2) = LCS(sub1, sub2) + e1。

总合以上分析，可以得到递迴公式：

LCS(s1, s2) =
 { LCS(sub1, s2) or LCS (s1, sub2) or LCS(sub1, sub2) , when e1 != e2
 { LCS(sub1, sub2) + e1                               , when e1 == e2

经过焠鍊简化：

LCS(s1, s2) =
 { max( LCS(sub1, s2), LCS(s1, sub2) ) , when e1 != e2
 { LCS(sub1, sub2) + e1                , when e1 == e2

最后考虑初始值。当 s1 或 s2 是空集合，则 LCS 是空集合。

逐步削减尾端元素，将原问题缩小以求得解。

计算 Longest Common Subsequence 的长度

二维阵列 array[i][j]，代表“s1 前 i 个元素”和“s2 前 j 个元素”的 LCS 长度。

Longest Common Subsequence: Hirschberg's Algorithm

演算法

http://en.wikipedia.org/wiki/Hirschberg's_algorithm

从中央分割，节省空间。空间複杂度为 O(min(X,Y))。也有人省略了 min 函数，直接写成 O(N)。

Longest Common Subsequence: Hunt-Szymanski Algorithm

LCS 问题转换成二维 LIS 问题

从 LCS 问题的 DP 表格可以观察到，LCS 问题可以化作类似于 LIS 的问题：从两序列中找出对应的相同元素，以位置数对表示；这些位置数对可以排出的最长严格递增序列，即是两序列的 LCS。

【注：这个类似于 LIS 的问题，就像是二维版的 LIS。不过“二维 LIS”目前没有正式定义。】

(1) A LCS problem:

  index: 0 1 2 3 4 5 6 7 8 9
  --------------------------
  s1:    a b a c d
  s2:    d b a a b c a

(2) All matched positions, with the matched character:

    a     a     a     a     a     a     b     b     c     d
  (0,2) (0,3) (0,6) (2,2) (2,3) (2,6) (1,1) (1,4) (3,5) (4,0)

(3) Here is the corresponding 2D table:

      d b a a b c a
    +---------------
  a |     * *     *
  b |   *     *
  a |     * *     *
  c |           *
  d | *

(4-1) { LCS == 2D LIS } example:

  LCS   :   a     b     a
  2D LIS: (0,2) (1,4) (2,6)　数对呈严格递增，在表格中则是往右下走。

      d b a a b c a
    +---------------
  a |     x *     *
  b |   *     x
  a |     * *     x
  c |           *
  d | *

(4-2) Another { LCS == 2D LIS } example:

  LCS   :   b     a     c
  2D LIS: (1,1) (2,2) (3,5)  数对呈严格递增，在表格中则是往右下走。

      d b a a b c a
    +---------------
  a |     * *     *
  b |   x     *
  a |     x *     *
  c |           x
  d | *

二维 LIS 问题转换成一维 LIS 问题

首先将所有数对排序，规则是第一个维度由小到大排序，当第一个维度相等时，第二个维度由大到小排序。排序之后，第二个维度的 1D LIS，就对应到原数对们的 2D LIS。

(1) 先将所有数列排序。
    第一维由小到大，当第一维相等时，第二维由大到小。
　　（排序规则亦可改成以第二个维度为主，最后则是找第一个维度的 1D LIS。）

    a     a     a     b     b     a     a     a     c     d
  (0,6) (0,3) (0,2) (1,4) (1,1) (2,6) (2,3) (2,2) (3,5) (4,0)

(2) 依序取出第二个维度的数值。

  6 3 2 4 1 6 3 2 5 0

(3) 这个序列的 1D LIS，对应到数对们的 2D LIS。其实也就是一开始要求的 LCS。

  6 3 2 4 1 6 3 2 5 0
      * *   *

  1D LIS:   2     4     6
  2D LIS: (0,2) (1,4) (2,6)   （注：第一个维度之前有排序）
  LCS   :   a     b     a
  
(4) 简洁的表达方式是：

     a b a c d                                s1 字串
  -> { a(6,3,2) b(1,4) a(6,3,2) c(5) d(0) }   s1 在 s2 当中出现的位置（由后往前）
  -> { 6 3 2 1 4 6 3 2 5 0 }                  依序取出第二个维度的数值
  -> 2 4 6                                    LIS

演算法

先把 LCS 问题看成二维 LIS 问题，再把二维 LIS 问题转成一维 LIS 问题，然后用 Robinson-Schensted-Knuth Algorithm 来算 LIS。

这裡以 s1 = cbaa、s2 = abcaa 为例。大意为：依序看 s1 的每个元素，是不是能让目前的 common subsequece 变得更长。

  | s2:   | 目前可生成的    | 截至目前最理想的
  | abcaa | 最长共同子序列  | 最长共同子序列
--+-------+-----------------+-------------
c | ..c.. |  ..c..          | 3
--+-------+-----------------+-------------
b | .b... |  .b...          | 2
--+-------+-----------------+-------------
a | ....a |  .b..a          | 2 5
  | ...a. |  .b.a.          | 2 4
  | a.... |  a.... & .b.a.  | 1 4	// 同时记录到两个
--+-------+-----------------+-------------
a | ....a |  a...a & .b.aa  | 1 4 5
  | ...a. |  a..a.          | 1 4 5
  | a.... |                 | 1 4 5	// 演算法结束

时间複杂度

先行判断两个序列的长度，将长度短的当作是 s1，那麽时间複杂度就会是 O(K * log(min(N,M)))，其中 K 为位置数对的总数目，N 和 M 分别是两序列长度。也有人省略了 min 函数，直接写成 O(KlogN)。K 最大可到 N * M，遇到了极端的例子时，会跑得比用 DP 还慢。

实作的时候会利用 counting sort 的技巧，先扫描一遍 s2，把 s2 每个字元的位置记下来，以符合时间複杂度。

计算 Longest Common Subsequence 的长度（两序列自身皆无重複元素）

计算 Longest Common Subsequence 的长度

这裡再提供一个不使用 binary search 的程式码，有时候会跑得比较快，各位可视情况採用之。

Longest Common Subsequence: Four-Russians Speedup（Kronrod's Algorithm）

Four-Russians Speedup

http://par.cse.nsysu.edu.tw/paper/2004/041204/FourRussiansSpeedup.ppt

Longest Common Increasing Subsequence

Longest Common Increasing Subsequence（LCIS）

严格递增的 LCS。LIS 的 DP 演算法稍作修改，即得 LCIS，时间複杂度仍是 O(N*M)。

UVa 12511 CF 10D

Cyclic Longest Common Subsequence

http://arxiv.org/pdf/1208.0396v3.pdf

ICPC 5890

Shortest Common Supersequence

找到一个最短的字串，其子序列包含了所有给定字串。

NP-hard。如果给定字串只有两个，可以使用 Dynamic Programming 解决。

SCS 长度，等于所有字串长度总和、再减去 LCS 长度。

UVa 10723