Najdłuższy wspólny podciąg
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
In the Vinony graph
Within Vinony's link graph, Najdłuższy wspólny podciąg is referenced by 79 other articles, and connects out to Ron Rivest, diff and computer science.
It sits within the topics Combinatorics, Dynamic programming and NP-complete problems.
Its subject is documented across 19 Wikipedia language editions.
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 · Polski
Najdłuższy wspólny podciąg (NWP, ang. longest common subsequence) – najdłuższy podciąg znaków, które występują w tej samej kolejności w dwóch porównywanych łańcuchach. Elementy podciągów nie muszą przy tym leżeć obok siebie (tym różni się ten problem od problemu najdłuższego wspólnego podłańcucha, ang. longest common substring). Rozwiązanie tego problemu jest bardzo przydatne przy pisaniu programów mających na celu wykrycie zmian w dokumentach lub plikach, lub przy pisaniu programów służących do identyfikacji plagiatów. Przykłady: * Dla ciągów abaabbaaa i babab ich NWP to baba i abab. * Dla ciągów POLITECHNIKA i TOALETA ich NWP to OLTA i OLEA. * Dla ciągów 123 oraz 543 ich NWP to 3. Warto przy tym zaznaczyć, że implementacja rozwiązania problemu może dotyczyć zarówno ciągu rozumianego jako ciąg liter, wyrazów czy nawet akapitów.
Abstract from DBpedia / Wikipedia · CC BY-SA