最長共通部分列問題
２つの列 $X$, $Y$ が以下のように与えられます。
$$X = (x_1, x_2, ..., x_m) $$
$$Y = (y_1, y_2, ..., y_n)$$
与えられた列の集合の最長共通部分列（Longest-common subsequence problem, LCS）を見つける問題を解きます。たとえば pencil と penguin のLCSは peni の４文字です。
列 $X$ の接頭辞（先頭 $i$ 文字までの文字列）を $X_i$、列 $Y$ の接頭辞（先頭 $j$ 文字までの文字列）を $Y_j$ としたとき、 $X_i$ と $Y_j$ のLCSの長さ $LCS (X_i, Y_j)$ は次のように動的計画法で計算できます。
LCS (X_i, Y_j) = \left\{
\begin{array}{ll}
0 & if \quad i = 0 \quad or \quad j = 0 \\
LCS (X_{i-1}, Y_{j-1}) + 1 & if \quad x_i = y_j \\
max \Bigl(LCS (X_{i}, Y_{j-1}), LCS (X_{i-1}, Y_{j}) \Bigr) & otherwise
\end{array}
\right.
またこの解法は、生命情報学（バイオインフォマティクス）という分野で日常的に用いられる配列相同性検索の基礎となるものです（実際には、文字列同士の類似性を考慮したもっと巧妙な手法を用います）。
課題４３：最長共通部分列
長さ $n$ の文字列 $s$ と、長さ $m$ の文字列 $t$ を入力としたとき、その２つの文字列の最長共通部分列の長さを求める関数を作ってください。
ただし、
- 1 ≤ $n$ ≤ 104
- 1 ≤ $m$ ≤ 104
とします。
- 例1
s = "pencil"
t = "penguin"
4
- 例2
s = "dreamingly"
t = "dreadfully"
6
- 例3
s = "This is a pen. This is an apple."
t = "pen-pineapple-apple-pen"
10
- 例4
s = "There is more to life than increasing its speed. "\
"(by Mahatma Gandhi)"
t = "There is always light behind the clouds. "\
"(by Louisa May Alcott)"
31
- 例5
s = "If you want to be successful, it's just this simple: "\
"Know what you are doing, love what you are doing, "\
"and believe in what you are doing. "\
"(by Will Rogers)"
t = "Success is not the key to happiness. "\
"Happiness is the key to success. "\
"If you love what you are doing, "\
"you will be successful. "\
"(by Louisa May Alcott)"
71
課題提出方法
-
基本的にGoogle Colaboratoryを用いてプログラミングしてください。どうしても Google Colaboratory を用いることができない場合のみ、Jupyter Notebook または Jupyter Lab を用いてください。
-
課題１つごとに、ノートブックを新規作成してください。１つのノートブックで複数の課題を解かないでください。
-
ノートブックを新規作成すると「Untitled.ipynb」のような名前になりますが、それを「学籍番号・氏名・課題番号」のような名前に変更してください。
-
質問・感想・要望などございましたらぜひ書き込んでください。
-
もし課題を解くにあたって参考になったウェブサイトがあれば、それについても触れてください。
-
課題を計算し終わった ipynb ファイルを提出するときは、指定したメールアドレスに Google Drive で共有する形で授業担当者に提出してください。