🔍 テキスト差分チェッカー

計算の仕組み

このツールは、2つのテキストを行ごとに分け、「最長共通部分列（LCS）」を求めることで差分を計算しています。LCSとは、両方のテキストに同じ順番で現れる行を、並びを保ったまま最も多く選んだものです。 LCSに含まれる行は「変更なし」、変更前にしかない行は「削除」、変更後にしかない行は「追加」として表示します。計算には、変更前の行数 × 変更後の行数の大きさの表を作り、表の後ろから「残りの部分で一致できる行の最大数」を埋めていく動的計画法を使っています。 この方法は、git diff などで使われる差分アルゴリズムと同じく、「できるだけ多くの行を変更なしとして残す」結果を求めます。そのため、行の順番を入れ替えた場合は、片方が削除・もう片方が追加として表示されます。