Родительская строка двух заданных строк
Учитывая 2 строки, мы должны найти строку наименьшей длины, такую, что указанные строки являются подпоследовательностями строки. Другими словами, нам нужно найти такую строку, чтобы удаление некоторых символов привело к заданным строкам. думал о грубой силе и LCS, но тщетно.
12345 и 11234 должны привести к 112345
WWA и WWS имеют ответ WWAS
LCS довольно неэффективна по памяти (DP), а грубая сила — просто ребячество. Что я должен делать?
Решение
Возможно, вы могли бы сделать глобальное выравнивание с Needleman-Wunsch и высокий штраф за несоответствие, чтобы отдать предпочтение Indels. В конце объедините выравнивание в «родительскую строку», взяв буквы из совпадающих позиций, а затем букву из любой из вставленных букв, например:
WW-A
||
WWS-
WWSA
Или же:
-12345
||||
11234-
112345
Память есть O (нм), но модификация сужает это до O (мин (п, т)).
Другие решения
В стандартной библиотеке есть четко определенный алгоритм, который будет служить вашим целям.
set_union ();
Условие — ваши входные диапазоны должны быть отсортированы.