Najkrótszy wspólny nadłańcuch (NWN, ang. Shortest Common Supersequence, SCS problem) – problem, najczęściej w informatyce i naukach z niej korzystających (np. bioinformatyka), polegający na poznaniu najkrótszego ciągu zawierającego elementy dwóch (lub więcej) ciągów w kolejności, w jakiej te elementy w tych ciągach występują. Problem ten można rozwiązać przy pomocy najdłuższego wspólnego podciągu, jako że dla dwóch ciągów A i B najkrótszy wspólny nadłańcuch jest różnicą między sumą długości ciągów A i B oraz najdłuższego wspólnego podciągu tych ciągów.
Przykład
Weźmy takie ciągi jak:
- POLITECHNIKA
- POPRAWA
- PELERYNA
Najkrótszym wspólnym nadłańcuchem jest POPELITERACHWYNIKA:
PO LITE CH NIKA
|| |||| || ||||
POP ||||RA||W |||A
||| ||||||||| ||||
P||EL||ER||||YN||A
||||||||||||||||||
POPELITERACHWYNIKA
