Корректировка любопытства
Любопытство — это марсоход, исследующий кратер Гейла на Марсе. Недавно он обнаружил доказательства наличия воды в марсианском грунте, что облегчит планирование будущих пилотируемых миссий.
Curiosity может напрямую связываться с Землей на скорости до 32 Кбит/с, но в среднем требуется 14 минут и 6 секунд для передачи сигналов между Землей и Марсом.
"Вы только что увидели камень и нажали на тормоза, но знаете, что марсоход уже проехал этот камень", — объясняет Мэтт Хеверли, водитель марсохода. "Поэтому мы просто планируем маршрут, затем записываем список простых текстовых команд: двигаться на один метр вперед, повернуть налево, сделать фото и так далее".
Иногда необходимо очень быстро реагировать на неожиданные события. Например, если камеры заметили что-то интересное, то вы можете захотеть изменить маршрут марсохода, чтобы сделать дополнительное фото. Для этого вы отправляете команду замены вида s///g. Это заменяет все вхождения, начиная с самого левого, на .
Более формально, если A — непустая строка, а B — строка, то для применения команды замены s/A/B/g к строке S следует сделать следующее:
Найдите самое левое вхождение A в S, такое что S = SL + A + SR.
Если такого вхождения нет, остановитесь. Тогда S — это ответ.
Пусть R будет результатом применения s/A/B/g к SR.
Ответ — это SL + B + R.
Это означает, что:
Если в S есть два перекрывающихся вхождения A, заменяется только самое левое. Например, применение "s/aba/c/g" к "abababa" дает "cbc": после замены первого вхождения "aba" строка превращается в "cbaba", и только последнее вхождение "aba" может быть заменено после этого.
Ни одна замена не использует результаты предыдущих замен. Например, применение "s/a/ab/g" к "a" дает "ab", применение "s/a/ba/g" к "a" дает "ba".
Вы знаете, что чем длиннее команда, тем больше времени необходимо для ее передачи. Поэтому вам нужно написать программу, которая находит самую короткую команду, преобразующую начальную строку в конечную строку.
Входные данные
Первая строка содержит начальную и конечную строки. Обе строки непусты, и их длина не превышает 2000 символов. Строки содержат только английские буквы, пробелы и знаки препинания (запятые, двоеточия, точки с запятой и дефисы: ',', ':', ';', '-'). Данные строки не равны.
Выходные данные
Выведите команду замены, которая преобразует начальную строку в конечную строку и имеет минимальную длину. Если существует несколько самых коротких команд замены, выведите любую из них.