Hardprob/Shortest Common Superstring — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Конечный алфавит <em>Σ</em>, конечный набор <em>R</em> стро…») |
(нет различий)
|
Версия 16:19, 11 апреля 2023
- Конечный алфавит Σ, конечный набор R строк из .
- Найти строку , такую что каждая строка является ее подстрокой, т.е.
, для каких-то .
- Минимизировать длину этой суперстроки .
Задача в лаб22 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «SR9»