最長共通部分列問題

ウィキペディア

最長共通部分列問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/01/20 02:07 UTC 版)

「最長共通部分文字列問題」とは異なります。

最長共通部分列問題（さいちょうきょうつうぶぶんれつもんだい、英: Longest-common subsequence problem, LCS）とは、与えられた列の集合（しばしば、2つの列からなる集合）の最長共通部分列を見つけ出す問題である。（ここで部分列(subsequence)は、部分文字列(substring)とは異なることに注意する。前者は元の列の連続した項からなる必要はない。）例えば、「ABCX」と「AYBZC」との最長共通部分列は「ABC」である。この問題は計算機科学における古典的問題であり、diff などのファイル比較プログラムの基礎をなし、バイオインフォマティクスにも応用されている。

計算量

入力列の個数が任意である一般の場合については、この問題はNP困難である。入力列の個数が一定のときには、この問題は動的計画法によって多項式時間で解く事ができる（後の項参照）。${\displaystyle N}$