最長共通部分列問題
Xi と Yj に対する最長共通部分列を見つけるため、xi と yj を比較する。もし、それらが同じであれば、その時は配列LCS(Xi-1, Yj-1) は、要素xiによって伸長されたものである。もしそれらが同じでなければ、その時は二つの配列の長さLCS(Xi, Yj-1), と LCS(Xi-1, Yj)は維持される。(もしそれらが両方とも同じ長さであり、しかし一致していない場合、その時は両方とも維持される) 注釈:添え字は、これらの公式によって1短縮される。結果は0の添え字も可能である。配列要素は、1から開始すると定義し、それは空の最長共通部分列(その時、添え字はゼロ)を追加する必要がある。