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

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

HotLog


 

Преобразователь строк

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

Преобразователь строк - это специальная компьютерная программа. Она получает на вход строку S и набор правил преобразования строки. Каждое из правил имеет вид c1c2 → E, где c1 и c2 - маленькие буквы латинского алфавита. Символом E здесь обозначена пустая строка. При этом каждый символ присутствует не более, чем в одном правиле.

Преобразователь строк работает по шагам. За один шаг он находит в текущей строке подстроку, совпадающую с правой частью одного из правил, после чего эта подстрока удаляется из текущей строки (этот процесс называется применением правила). Этот процесс продолжается до тех пор, пока существует правило, которое можно применить. Строка, которая остается к моменту, когда нельзя применить никакое правило, считается результатом T работы преобразователя строк.

Пусть, например, набор правил таков: {ab → E, cd → E}, а исходная строка S = aabbccdba. Тогда работа преобразователя будет выглядеть так: aabbccdba → abccdba → ccdba → cba, и результатом T работы преобразователя будет строка cba.

Ваша задача состоит в том, чтобы написать программу, моделирующую работу преобразователя строк с заданным набором правил на заданной строке S.

Входные данные

Первая строка входного файла INPUT.TXT содержит целое число n (0 ≤ n ≤ 13) - количество правил. Далее идут n строк, каждая из которых описывает одно из правил. Гарантируется, что каждая из маленьких букв латинского алфавита присутствует не более, чем в одном правиле.

Последняя, (n+2)-ая строка входного файла содержит исходную строку S. Она не пуста и состоит только из маленьких букв латинского алфавита. Длина S не превосходит 100000.

Выходные данные

В выходной файл OUTPUT.TXT выведите строку T - результат работы преобразователя на строке S.

Примеры

INPUT.TXTOUTPUT.TXT
12
ab
cd
aabbccdba
cba
20
abcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxyz

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

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

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