Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Подстрока

(Время: 1 сек. Память: 32 Мб Сложность: 58%)

Рассмотрим слова, состоящие из букв «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.TXTOUTPUT.TXT
1abAaBBabbA
AaBaba
aAaBabaAbA

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483