Najkrótszy wspólny nadłańcuch

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

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