アルゴリズム1000本ノック #3. Longest common subsequence

#### Problem

```
文字列S1とS2の最長共通部分を求めよ. 最長共通部分とは,
S1とS2の要素から順番を保ったまま任意の数の文字を選択した場合に
同一となる文字列のうち, 最長のものを指す.
たとえば, "1224533324" と "69283746" の最長共通部分は "234"である.
```

#### Solution
これも有名なDPの問題の1つです. 個人的にはめちゃくちゃ難しいと思います….
[Longest Common Substring](http://qiita.com/_rdtr/items/b80cecac36451dbaee60)と似ていますが, **必ずしも要素同士は隣り合っている必要がない**という点が異なります.

問題の例について考えてみます. 与えられた２つの文字列を縦と横に置いて, 下の図のようなテーブルを考えます.

![example1](http://f.st-hatena.com/images/fotolife/r/rdtr/20151103/20151103225640.png?1446620237)

例えばオレンジ色のセル `Table[4][2]` は `S1.subString(0, 5) = "12245"` と `S2.subString(0, 3) = "692"`の最長共通部分の長さを格納することになります. この問題を解くということは, この表のすべての値を埋めることと同一です.

![example2](http://f.st-hatena.com/images/fotolife/r/rdtr/20151103/20151103230039.png?1446620452)

0行目, 0列目から考えます. 例えば0行目, これは `"1224533324" は "6" を含むか? "6" を見つけるまでは "0" を, もし見つけたら以降は "1" を埋めよ` という問題になります. 残念ながら我々のケースでは `"6"` は見つからないので, 値はすべて`"0"`になります. 列についても同様です.

![example3](http://f.st-hatena.com/images/fotolife/r/rdtr/20151103/20151103233524.png?1446622533)

続いて `Table[1][1]` を見てみます. この場合, `S1[1] != S2[1]` ですので, その前段の状態, すなわち `Table[0][1]`, `Table[1][0]`, `Table[0][0]` から最長のLCSをそのまま引き継ぐことになります. ただし `Table[0][1] >= Table[0][0]`, `Table[1][0] >= Table[0][0]` が成り立つので ( `S1[1] == S2[0]` もしくは `S1[0] == S2[1]` の場合, `Table[0][1]` もしくは `Table[1][0]` は `Table[0][0] + 1` となるため),  `Table[0][0]` を無視して上か左のセルをチェックし, 大きい方を取れば良さそうです.

![example4](http://f.st-hatena.com/images/fotolife/r/rdtr/20151103/20151103235353.png?1446623644)

次は `Table[1][2]` で, `S1[1] == S2[2]` となっています! したがってLCSの長さを1伸ばすことができます. ここで私たちは同時に,  **Table[0][1] の状態から斜めにしかこのセルに到達できない** ことに気づきます. `Table[0][2]` と `Table[1][1]` においては, `S1[1]` あるいは `S2[2]` (= `"2"`) が既に考慮済のためです.

ここまで見てきたルールを一般化してみましょう.

```
Table[i][j] =
	Table[i-1][j-1] + 1 if S1[i] == S2[j]
	else
		Max(Table[i][j-1], Table[i-1][j])
```

これを順次適用することで, 表をすべて埋めることが可能です.

![example5](http://f.st-hatena.com/images/fotolife/r/rdtr/20151104/20151104000153.png?1446624166)

さて, LCSの最長の長さが分かりました. でも, LCSの文字列そのものが欲しい場合はどうしましょう？ LCSの長さが伸びるときはつねに斜め下にジャンプする, ということは分かっています. すなわち, LCSの文字列を集めるためには最終的に最長のLCSを得たケースにおいて, 表のどこでジャンプしたのかを調べればよいのです.

![example6](http://f.st-hatena.com/images/fotolife/r/rdtr/20151104/20151104013104.png?1446629490)

コレをチェックするために, テーブルの右下（最終パターン）から始めます.  **ジャンプしてきた地点においては, `S1[i] == S2[j]` が満たされているはずです**. この点を見つけるまで, セルの上か右に移動しつづけ(LCSの長さを保ちながら), 見つけたら文字を保存して斜め左上に飛んでLCSの長さも１減る, この手順をテーブルの左か上端に到達するまで続ければ良いことがわかります.

上の例では, `"4"`, `"3"`, `"2"` が保存されますが, これはまさにLCSの逆さまになった形です.
下のコードでは, テーブルの表現として `m[i][j]` を使っています.

```python:algorithms_dp_longest_common_subsequence.py
def LCS(s1, s2):
    l1, l2 = len(s1), len(s2)
    if l1 == 0 or l2 == 0: return ''
        
    # memorization of m[l1][l2]
    m = []
    for x in range(l1):
        m.append([0]*(l2))
    
    # Fill 0th row
    isSameFound = False
    for i in range(l1):
        if isSameFound or s1[i] == s2[0]:
            m[i][0] = 1
            isSameFound = True
    
    # Fill 0th column
    isSameFound = False
    for j in range(l2):
        if isSameFound or s2[j] == s1[0]:
            m[0][j] = 1
            isSameFound = True
        
    max_len = 0
    # m[i][j] stores the maximum length of subsequence of s1[:i+1], s2[:j+1]
    for i in range(0, l1-1):
        for j in range(0, l2-1):
            if s1[i+1] == s2[j+1]:
                m[i+1][j+1] = m[i][j] + 1
                max_len = max(m[i][j], max_len)
            else:
                m[i+1][j+1] = max(m[i][j+1], m[i+1][j])
    
    #If you want to know just the length of the lcs, return maxLen.
    #Here we'll try to print the lcs.
    lcs_str = ''
    i, j = l1-1, l2-1
    while i >= 0 and j >= 0:
        if s1[i] == s2[j]:
            lcs_str += s1[i] #or s2[j-1]
            i -= 1
            j -= 1
        else:
            if m[i-1][j] > m[i][j-1]:
                i -= 1
            else:
                j -= 1

    return lcs_str[::-1]
```

計算量は O(MN) + O(M+N) = O(MN),  
空間量は O(MN). (m[M][N]を保持するため).

\# M, N はそれぞれの文字列の要素数.

Jave版コードはこちら:

```java:algorithms_dp_longest_common_subsequence.java

import java.lang.Math;

public class Solution {
  public static String LCS(String s1, String s2) {
    if (s1.isEmpty() || s2.isEmpty()) {
      return "";
    }
    int l1 = s1.length();
    int l2 = s2.length();

    // memorization
    int[][] m = new int[l1][l2];
	int maxLen = 0;
	
	// fill the 0th row
	boolean isFound = false;
	for (int i = 0; i < l1; i++) {
		if (isFound || s1.charAt(i) == s2.charAt(0)) {
		    m[i][0] = 1;
		    isFound = true;
		} else {
		    m[i][0] = 0;
		}
	}
	
	// fill the 0th column
    isFound = false;
	for (int j = 0; j < l2; j++) {
		if (isFound || s2.charAt(j) == s1.charAt(0)) {
		    m[0][j] = 1;
		    isFound = true;
		} else {
		    m[0][j] = 0;
		}
	}
    
    // m[i][j] stores the maximum length of subsequence until s1.subString(0, i+1), s2.subString(0, j+1)
    for (int i = 1; i < l1; i++) {
        for (int j = 1; j < l2; j++) {
            if (s1.charAt(i) == s2.charAt(j)) {
                m[i][j] = m[i-1][j-1] + 1;
                maxLen = Math.max(m[i][j], maxLen);
        }   else {
                m[i][j] = Math.max(m[i-1][j], m[i][j-1]);
            }
        }
    }
    
    // If you want to know just the length of the lcs, return maxLen.
    // Here we'll try to print the lcs.
    StringBuilder sb = new StringBuilder();
    int i = l1 - 1, j = l2 - 1;
    while (i > 0 && j > 0) {
      if (s1.charAt(i) != s2.charAt(j)) {
        if (m[i-1][j] > m[i][j-1]) i--;
        else j--;
      } else {
        sb.append(s1.charAt(i)); // or s2.charAt(j-1)
        i--; j--;
      }
    }
    
    return sb.reverse().toString();
  }
}
```