Олимпиада проводится при поддержке Московского физико-технического института, Благотворительного фонда "Династия", компьютерной компании НИКС, Компании Yandex, компании Genius
Информационная поддержка:
журнал "Мир ПК"
III Всероссийская заочная олимпиада школьников по информатике, 2008/09 учебный год
Задача C. Шаблоны
| Имя входного файла: | c.in |
| Имя выходного файла: | c.out |
| Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайта |
Шаблоном называется строка, состоящая из маленьких латинских букв, символов * и ?. В шаблоне * может быть заменена на любую (в том числе пустую) последовательность маленьких латинских букв. Символ ? может быть заменен на любую одну маленькую латинскую букву. Если с помощью этих правил некоторая строка из маленьких латинских букв может быть получена из заданного шаблона, говорят, что она удовлетворяет этому шаблону.
Множество строк, удовлетворяющих шаблону (оно может быть как конечно, так и бесконечно), называется языком, порождаемым данным шаблоном.
Напишите программу, которая для двух заданных шаблонов отвечает на вопрос: верно ли, что язык, порождаемый первым шаблоном, является подмножеством языка, порождаемого вторым шаблоном (ответ на этот вопрос будет положительным и в том случае, когда эти языки совпадают).
Формат входных данных
Во входном файле записано три пары строк. Каждая строка задает шаблон. Длина каждого шаблона не превышает 250 символов.
Формат выходных данных
Выведите в выходной файл три строки, в каждой из которых должно быть выведено либо сообщение YES, либо NO. В первой строке - ответ на вопрос задачи для первого и второго шаблонов, во второй - для третьего и четвертого, в третьей - для пятого и шестого.
Пример
| c.in | c.out |
abcd ab?d abd ab*d abc* a?d |
YES YES NO |