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
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