Najkrótszy wspólny nadłańcuch

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