最長共通部分列関数定義
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/06/22 05:55 UTC 版)
「最長共通部分列問題」の記事における「最長共通部分列関数定義」の解説
二つの配列を以下のように定義する: X = (x1, x2...xm) … X の接頭辞は、 X1, 2,...m Y = (y1, y2...yn) … Y の接頭辞は、 Y1, 2,...n LCS(Xi, Yj) は、Xi と Yj の接頭辞の最長共通部分列セットを代表する。この配列セットは、以下を与える。 L C S ( X i , Y j ) = { ∅ if i = 0 or j = 0 L C S ( X i − 1 , Y j − 1 ) ⌢ x i if x i = y j longest ( L C S ( X i , Y j − 1 ) , L C S ( X i − 1 , Y j ) ) if x i ≠ y j {\displaystyle LCS\left(X_{i},Y_{j}\right)={\begin{cases}\emptyset &{\mbox{ if }}\ i=0{\mbox{ or }}j=0\\{\textrm {}}LCS\left(X_{i-1},Y_{j-1}\right)\frown x_{i}&{\mbox{ if }}x_{i}=y_{j}\\{\mbox{longest}}\left(LCS\left(X_{i},Y_{j-1}\right),LCS\left(X_{i-1},Y_{j}\right)\right)&{\mbox{ if }}x_{i}\neq y_{j}\\\end{cases}}} Xi と Yj に対する最長共通部分列を見つけるため、xi と yj を比較する。もし、それらが同じであれば、その時は配列LCS(Xi-1, Yj-1) は、要素xiによって伸長されたものである。もしそれらが同じでなければ、その時は二つの配列の長さLCS(Xi, Yj-1), と LCS(Xi-1, Yj)は維持される。(もしそれらが両方とも同じ長さであり、しかし一致していない場合、その時は両方とも維持される) 注釈：添え字は、これらの公式によって1短縮される。結果は0の添え字も可能である。配列要素は、1から開始すると定義し、それは空の最長共通部分列(その時、添え字はゼロ)を追加する必要がある。
※この「最長共通部分列関数定義」の解説は、「最長共通部分列問題」の解説の一部です。
「最長共通部分列関数定義」を含む「最長共通部分列問題」の記事については、「最長共通部分列問題」の概要を参照ください。
- 最長共通部分列関数定義のページへのリンク
