|
Подстрока
(Время: 1 сек. Память: 32 Мб Сложность: 68%)
Рассмотрим слова, состоящие из букв «A», «B», «a» и «b». Скажем, что два слова эквивалентны, если одно может быть получено из другого с помощью следующих операций:
- удалить в любой позиции подстроку, равную Aa, aA, Bb или bB;
- добавить в любую позицию подстроку, равную Aa, aA, Bb или bB.
Например, слова abAaBBabbA и aAaBabaAbA эквивалентны:
abAaBBabbA → abBBabbA → aBabbA → aAaBabbA → aAaBabaAbA,
а слова abAB и baBA - нет.
Интересно отметить, что для произвольных слов X и Y найдется такое слово Z, эквивалентное X, которое содержит Y в качестве подстроки. Ваша задача - найти кратчайшее такое слово.
Входные данные
Первая строка входного файла INPUT.TXT содержит X. Вторая строка содержит Y. Оба слова непустые и каждое из них имеет длину не больше 2000.
Выходные данные
В выходной файл OUTPUT.TXT выведите одну строку, содержащую минимальное по длине слово, эквивалентное X, содержащее Y в качестве подстроки. Если решений несколько, выведите любое.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | abAaBBabbA
AaBaba | aAaBabaAbA |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
