列X＝{x₁，x₂，…，x_n}に対して，順序を保持して要素を抽出した列を部分列という。また，列の長さはその列の要素の個数で定義される。ここでは，各要素が文字である列を考える。例えば，X＝{"A"，"B"，"C"，"B"，"D"，"A"，"B"} のとき，図1に示すように{"B"，"C"，"D"，"B"}はXの部分列の例であり，その長さは4である。　ある列Zが二つの列X，Y両方の部分列であるとき，ZをXとYとの共通部分列といい，共通部分列のうち長さが最大となるものを最長共通部分列という。最長共通部分列は複数通り存在する場合もあるが，その長さは一意に決まる。X＝{"A"，"B"，"C"，"B"，"D"，"A"，"B"}，Y＝{"B"，"D"，"C"，"A"，"B"，"A"}の場合の共通部分列及び最長共通部分列の例を図2に示す。　なお，共通部分列が存在しない場合，最長共通部分列は空の列となり，その長さは0である。
　最長共通部分列の長さは，2本のDNAの塩基配列間の類似度を測る目的などに用いられる。

〔最長共通部分列の長さを求めるアルゴリズム〕
　二つの列X，Yの最長共通部分列の長さを求めるアルゴリズムを考える。列X，Yそれぞれについて，先頭からn個，k個の要素を抽出した列をX_n，Y_kと表記し，列X_n，Y_kそれぞれの末尾の要素をx_n，y_kと表記する。例えば，X＝{"A"，"B"}とすると，X₃＝{"A"，"B"，"C"}，x₃＝"C"である。このとき，列X_nと列Y_kとの最長共通部分列の中の一つをLCS(n，k)，最長共通部分列の長さをLCSL(n，k)と表記する。なお，X₀とY₀は空の列であり，x₀とy₀は存在しない。
　ここで，x_nとy_kとが一致しているか否かに着目して次の(1)～(3)に場合分けし，再帰的な関係を用いてLCSL(n，k)を求めることを考える。

• x_n＝y_kの場合を考える。例えば，x_n＝y_k＝"A"とする。このとき，LCS(n，k)の末尾の要素は"A"となる。よって，LCS(n，k)は，列X_n－1，Y_k－1の最長共通部分列LCS(n－1，k－1)の末尾に"A"を付加したものと一致する。したがって，LCSL(n，k)＝LCSL(n－1，k－1)＋1が成り立つ。
• x_n≠y_kの場合を考える。例えば，x_n＝"A"，y_k＝"B"とする。ここで，LCS(n，k)の末尾の要素は"A"又は"A"以外となる。LCS(n，k)の末尾の要素が"A"である場合は，列Y_kから末尾の"B"を取り除いても最長共通部分列には影響しないので，LCS(n，k)はLCS(n，k－1)と一致する。一方，LCS(n，k)の末尾の要素が"A"でない場合は，列X_nから末尾の"A"を取り除いても最長共通部分列には影響しないので，LCS(n，k)はLCS(n－1，k)と一致する。よって，LCS(n，k)はLCS(n，k－1)又はLCS(n－1，k)のいずれかと一致する。したがって，LCSL(n，k)は，LCSL(n，k－1)とLCSL(n－1，k)のうちの最大値と一致する。
• n＝0又はk＝0の場合，最長共通部分列は空の列となり，LCSL(n，k)＝0である。

〔動的計画法を用いて最長共通部分列の長さを求めるアルゴリズム]
　(1)～(3)の再帰的な関係に従い，LCSL(n，k)を再帰的に計算することによって，列X，Yの最長共通部分列の長さを求めることができる。しかし，再帰的に計算するアルゴリズムでは，重複して同じ計算をすることによって時間計算量が大きくなり，非効率になる場合がある。そこで，重複して同じ計算をすることを避けるために，LCSL(n，k)の値を動的計画法によって求めることを考える。
　二つの列がX＝{"A"，"B"，"C"，"B"，"D"，"A"，"B"}，Y＝{"B"，"D"，"C"，"A"，"B"，"A"} の場合，0≦n≦7かつ0≦k≦6に対するLCSL(n，k)の値を図3に示す。図3の左端2列はn(0～7)とそれに対応するx_nを，上端2行はk(0～6)とそれに対応するy_kを表す。n＝0のときのx_n，k＝0のときのy_kは存在しないので，"－"と表す。各要素は列X_n，と列Y_kとの最長共通部分列の長さLCSL(n，k)の値を示している。　図3の各要素の値は，〔最長共通部分列の長さを求めるアルゴリズム〕の(1)～(3)の再帰的な関係に従って求められる。
　まず，n＝0又はk＝0のときは(3)に対応するので，LCSL(n，k)＝0である。
　それ以外の値について，例えば，図3の①～③は次のように値が決まる。
　①について，x₂＝y₁なので(1)に対応し，LCSL(2，1)＝LCSL(1，0)＋1である。LCSL(1，0)＝0なので，LCSL(2，1)＝1となる。
　②について，x₂≠y₂なので(2)に対応し，LCSL(2，1)＝1，LCSL(1，2)＝0なので，LCSL(2，2)＝1となる。
　③について，X₆≠y₂なので(2)に対応し，LCSL(6，1)＝1，LCSL(5，2)＝2なので，LCSL(6，2)＝2となる。
　図3の要素の値を全て計算することによって列X，Yの最長共通部分列の長さが4であると分かる。

〔動的計画法を用いて最長共通部分列の長さを求めるプログラム〕
〔動的計画法を用いて最長共通部分列の長さを求めるアルゴリズム〕に基づいて，二つの列の最長共通部分列の長さを求めるプログラムを考える。任意の二つの列をそれぞれ配列S，Tとして受け取り，動的計画法を用いて最長共通部分列の長さを求めるプログラムを図4に示す。ここで，配列の要素番号は0から始まり，整数型の二次元配列 lcsl は，行番号が0から配列Sの要素数sまでの(s＋1)行，列番号が0から配列Tの要素数tまでの(t＋1)列の大きさをもつ。　図4のプログラムの時間計算量を，配列Sの要素数s, 配列Tの要素数tを用いて表すとO(キ)である。

列{"A"，"C"，"B"，"C"，"D"，"C"}と列{"C"，"D"，"B"，"D"，"C"，"A"}との最長共通部分列の長さを答えよ。

図3中のア，イに入れる適切な数値を答えよ。

図4中のウ～カに入れる適切な字句を答えよ。

本文中のキに入れる適切な字句を，sとtを用いて答えよ。