Рубрики

ВОРОТА | GATE-CS-2014- (Set-2) | Вопрос 47

Рассмотрим две строки A = «qpqrr» и B = «pqprqrp». Пусть x — длина самой длинной общей подпоследовательности (не обязательно смежной) между A и B, и пусть y — количество таких самых длинных общих подпоследовательностей между A и B. Тогда x + 10y = ___.
(А) 33
(Б) 23
(С) 43
(D) 34

Ответ: (D)
Объяснение: // LCS имеет длину 4. Есть 3 LCS длиной 4 «qprr», «pqrr» и qpqr

Подпоследовательность — это последовательность, которая может быть получена из другой последовательности, выбрав из нее ноль или более элементов без изменения порядка оставшихся элементов. Подпоследовательность не должна быть смежной. Поскольку длина заданных строк A = «qpqrr» и B = «pqprqrp» очень мала, нам не нужно строить матрицу 5 × 7 и решать ее с помощью динамического программирования. Скорее мы можем решить это вручную просто грубой силой. Сначала мы проверим, существует ли подпоследовательность длины 5, так как min_length (A, B) = 5.

Рекомендуемые посты:

ВОРОТА | GATE-CS-2014- (Set-2) | Вопрос 47

0.00 (0%) 0 votes