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
Kategoria:Algorytmy aproksymacyjne Kategoria:Programowanie dynamiczne