Editing Longest common subsequence (section)

{{Short description|Algorithmic problem on pairs of sequences}}
{{Distinguish|longest common substring}}
[[File:Nubio Diff Screenshot3.png|thumb|Comparison of two revisions of an example file, based on their longest common subsequence  (black)]]
A '''longest common subsequence''' ('''LCS''') is the longest [[subsequence]] common to all sequences in a set of sequences (often just two sequences). It differs from the [[longest common substring]]: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. The problem of computing longest common subsequences is a classic [[computer science]] problem, the basis of [[data comparison]] programs such as the [[diff utility|<code>diff</code> utility]], and has applications in [[computational linguistics]] and [[bioinformatics]]. It is also widely used by [[Revision control|revision control systems]] such as [[Git (software)|Git]] for [[Merge (revision control)|reconciling]] multiple changes made to a revision-controlled collection of files. 
<!-- todo: add definition and example -->

For example, consider the sequences (ABCD) and (ACBAD). They have five length-2 common subsequences: (AB), (AC), (AD), (BD), and (CD); two length-3 common subsequences: (ABD) and (ACD); and no longer common subsequences. So (ABD) and (ACD) are their longest common subsequences.