最長共通部分列問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/02/01 15:08 UTC 版)
最長共通部分列問題（さいちょうきょうつうぶぶんれつもんだい、英: Longest-common subsequence problem, LCS）とは、与えられた列の集合（しばしば、2つの列からなる集合）の最長共通部分列を見つけ出す問題である。（ここで部分列(subsequence)は、部分文字列(substring)とは異なることに注意する。前者は元の列の連続した項からなる必要はない。）例えば、「ABCX」と「AYBZC」との最長共通部分列は「ABC」である。この問題は計算機科学における古典的問題であり、diff などのファイル比較プログラムの基礎をなし、バイオインフォマティクスにも応用されている。
- ^ L. Bergroth and H. Hakonen and T. Raita (2000). “A Survey of Longest Common Subsequence Algorithms”. SPIRE (IEEE Computer Society) 00: 39–48. doi:10.1109/SPIRE.2000.878178. ISBN 0-7695-0746-8.
- ^ Ronald I. Greenberg (6 August 2003). "Bounds on the Number of Longest Common Subsequences". arXiv:cs.DM/0301030。
- ^ Xia, Xuhua (2007). Bioinformatics and the Cell: Modern Computational Approaches in Genomics, Proteomics and Transcriptomics. New York: Springer. p. 24. ISBN 0-387-71336-0
[続きの解説]
「最長共通部分列問題」の続きの解説一覧
- 最長共通部分列問題のページへのリンク
