Metraipolis › archive › dc_948c2edd2fbb

Longest common subsequence — Wikipedia (en)

Source: Wikipedia (en)
Original: https://en.wikipedia.org/wiki/Longest_common_subsequence
License (as archived): CC-BY-SA-4.0
Archived: 2026-10-07T14:25:53.378Z
SHA-256 of the archived text: b7e508bb9d2a59d0076674de2366d85009ba0179c2b77694536aadd8ad52fa8a
Stable URL of this page: https://metraipolis.com/documento/dc_948c2edd2fbb

How to cite

Longest common subsequence — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Longest_common_subsequence (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_948c2edd2fbb (Metraipolis archive dc_948c2edd2fbb, sha256 b7e508bb9d2a59d0076674de2366d85009ba0179c2b77694536aadd8ad52fa8a)

BibTeX

@misc{dc948c2edd2fbb,
  title = {Longest common subsequence — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Longest_common_subsequence},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_948c2edd2fbb; sha256 b7e508bb9d2a59d0076674de2366d85009ba0179c2b77694536aadd8ad52fa8a},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Longest_common_subsequence. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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, elements of 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. Because it is polynomial and has an efficient algorithm to solve it, it is employed to compare data and merge changes to files in programs such as the diff utility and revision control systems such as Git. It has similar applications in computational linguistics and bioinformatics. 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.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; categoria «Combinatorics»).
Fonte: Wikipedia in inglese, voce «Longest common subsequence» — https://en.wikipedia.org/wiki/Longest_common_subsequence
Wikidata Q141001 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q141001
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Longest_common_subsequence?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1375229678, consultata il 2026-10-07T14:07:14.025Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: e1a2733186407511e2d070e0dad2a8cc1260ca655b375bc986c45a97cb9b5bfb