Наибольшая общая подпоследовательность

@Abricos47 · Регистрация: 12.06.2020

Author24 — интернет-сервис помощи студентам

Общей подпоследовательностью двух строк s1 и s2 называется пара последовательностей индексов ({ai},{bi}) такая, что a1 < a2 < … < ak, b1 < b2 < … < bk, and s1[ai]=s2[bi] for all 1≤ i≤ k.

Найдите наибольшую общую подпоследовательность двух строк.

Формат ввода
Первая и вторая строки входа содержат две непустые строки, каждая из которых состоит из строчных латинских букв. Длина каждой строки не превосходит 100.

Формат вывода
В первой строке выведите целое число k — длину наибольшей общей подпоследовательности. Во второй выведите k целых чисел — индексы символов наибольшей общей подпоследовательности в первой строке, отсортированные по возрастанию. В третьей, аналогично — отсортированные по возрастанию индексы символов наибольшей общей подпоследовательности во второй строке. Символы в строках занумерованы с 1.

Если способов выбрать наибольшую общую подпоследовательность несколько, выведите любой из них.

Ввод
abcd
cxbydz

Вывод
2
3 4
1 5

@palva · 14.06.2020, 10:53

https://youtu.be/m4HOkVeN4Mo?t=1727

@Abricos47 · 14.06.2020, 10:55 **[ТС]**

Видео не грузит

@palva · 14.06.2020, 10:58

Заменил.

@Abricos47 -8 / 0 / 0 Регистрация: 12.06.2020 Сообщений: 35
		1
	Наибольшая общая подпоследовательность 14.06.2020, 10:26. Показов 8075. Ответов 3 Метки нет (Все метки) Общей подпоследовательностью двух строк s1 и s2 называется пара последовательностей индексов ({ai},{bi}) такая, что a1 < a2 < … < ak, b1 < b2 < … < bk, and s1[ai]=s2[bi] for all 1≤ i≤ k. Найдите наибольшую общую подпоследовательность двух строк. Формат ввода Первая и вторая строки входа содержат две непустые строки, каждая из которых состоит из строчных латинских букв. Длина каждой строки не превосходит 100. Формат вывода В первой строке выведите целое число k — длину наибольшей общей подпоследовательности. Во второй выведите k целых чисел — индексы символов наибольшей общей подпоследовательности в первой строке, отсортированные по возрастанию. В третьей, аналогично — отсортированные по возрастанию индексы символов наибольшей общей подпоследовательности во второй строке. Символы в строках занумерованы с 1. Если способов выбрать наибольшую общую подпоследовательность несколько, выведите любой из них. Ввод abcd cxbydz Вывод 2 3 4 1 5 0

@palva 4240 / 2937 / 687 Регистрация: 08.06.2007 Сообщений: 9,817 Записей в блоге: 4
	14.06.2020, 10:53	2
	https://youtu.be/m4HOkVeN4Mo?t=1727 0

@Abricos47 -8 / 0 / 0 Регистрация: 12.06.2020 Сообщений: 35
	14.06.2020, 10:55 [ТС]	3
	Видео не грузит 0

@palva 4240 / 2937 / 687 Регистрация: 08.06.2007 Сообщений: 9,817 Записей в блоге: 4
	14.06.2020, 10:58	4
	Заменил. 0