最長共通部分列問題
これから C = (AGCAT)と R = (GAC)の共通の最長部分列を見つける。最長共通部分列関数は、ゼロ番目の要素を使用する。それは、ゼロ接頭辞を定義するのに便利であり、配列C0 = Ø; と R0 = Øは空である。すべての接頭辞は、テーブル上で最初の縦列 C (これは列ヘッダとなる)と、最初の横列 R (これは行ヘッダとなる)である。
このテーブルは、最長共通部分列のそれぞれの計算手順を保存するために使われ、二つ目の縦列と二つ目の横列はØで埋まっている。なぜなら、空配列は非空配列と比較されたとき、最長共通部分列はいつでも空配列である。
LCS(R1, C1)は、それぞれの配列の最初の要素と比較することによって決定した。G と A は、同じ長さではない、そう、その最長共通部分列は二つの最長配列、LCS(R1, C0) と LCS(R0, C1)を得る。(二つ目の特質を使用する) 続くテーブル、それら両方の空白は、LCS(R1, C1)も空白である。同じように、以下のテーブルも見えてくる。矢印は、配列が上のセル、LCS(R0, C1)と左のセル、LCS(R1, C0)の両方のセルから来ることを示している。
LCS(R1, C2) は、G と G を比較し決定された。それは一致している、そう、G は左上の配列LCS(R0, C1) に追加される。それは、(Ø)であり、(ØG)を与え、それは、(G)です。