最長共通部分列問題
Sign in to saveAlso known as LCS
the problem of finding a sequence that is a subsequence of each of a given set of sequences and is as long as possible
Wikidata facts
- Instance of
- computational problem
Show 4 more facts
- Stack Exchange tag
- stackoverflow.com/tags/lcs
- different from
- longest common substring problem
- computational complexity
- NP-complete
- short name
- LCS
via Wikidata · CC0
Article · 日本語
最長共通部分列問題（さいちょうきょうつうぶぶんれつもんだい、英: Longest-common subsequence problem, LCS）とは、与えられた列の集合（しばしば、2つの列からなる集合）の最長共通部分列を見つけ出す問題である。（ここで部分列(subsequence)は、部分文字列(substring)とは異なることに注意する。前者は元の列の連続した項からなる必要はない。）例えば、「ABCX」と「AYBZC」との最長共通部分列は「ABC」である。この問題は計算機科学における古典的問題であり、diff などのファイル比較プログラムの基礎をなし、バイオインフォマティクスにも応用されている。
Abstract from DBpedia / Wikipedia · CC BY-SA