Najdłuższy wspólny podłańcuch (NWP, ang. longest common substringtłumaczenie nazwy według ) 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
Kategoria:Programowanie dynamiczne