Najdłuższy wspólny podłańcuch
Najdłuższy wspólny podłańcuch (NWP, ang. longest common substring[1]) danych dwóch ciągów X i Y – najdłuższy możliwy podciąg elementów leżących obok siebie w ciągach X i Y. Zbliżonym pojęciem jest najdłuższy wspólny podciąg, którego elementy mogą jednak być rozdzielone w ciągach X i Y przez inne elementy tych ciągów.
Przykład[edytuj | edytuj kod]
Dla ciągów 'ABAB' oraz 'BABA' najdłuższy wspólny podłańcuch to 'BAB' lub 'ABA' natomiast dla trzech ciągów 'ABAB' 'BABA' oraz 'ABBA' najdłuższy wspólny podłańcuch to 'AB' lub 'BA'. Pozostałe wspólne łańcuchy to 'A' 'B' oraz łańcuch pusty (które nie są rozwiązaniem problemu, gdyż poszukiwany jest najdłuższy)
ABAB ||| BABA || ABBA
Przypisy[edytuj | edytuj kod]
- ↑ tłumaczenie nazwy według Jerzy Wałaszek: Wyszukiwanie najdłuższego wspólnego podłańcucha. [dostęp 2016-02-08].