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