C. Сопоставление с шаблоном @ Личное первенство УрГУ 2002 @ Timus Online Judge

C. Сопоставление с шаблоном

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

При разработке очередной СУБД, вам поставили задачу реализовать оператор ‘like’. Оператор ‘like’ сравнивает текстовую строку с заданным шаблоном и говорит, удовлетворяет ли эта строка шаблону. Шаблон является текстовой строкой, в которой допустимы любые символы. При этом некоторые символьные последовательности шаблона имеют особый смысл:

%	допускает совпадение с любым количеством любых символов
_	допускает совпадение с любым одиночным символом
[с1-с2]	допускает совпадение с любым одиночным символом из диапазона c1-c2
[c1c2c3…cN]	допускает совпадение с любым одиночным символом из последовательности c1,c2,c3,…,cN
[^с1-с2]	допускает совпадение с любым одиночным символом не из диапазона с1-с2
[^c1c2c3…cN]	допускает совпадение с любым одиночным символом не из последовательности c1,c2,c3,…,cN

Исходные данные

В первой строке находится число N ≤ 1000. В следующих N строках находятся выражения для проверки совпадения строки с шаблоном в следующем формате:

'строка' like 'шаблон'

Строка или шаблон могут содержать любые символы с кодами 32-255. Если строка или шаблон содержат символ ' (ASCII 39), то этот символ удваивается. Максимальная длина строки или шаблона — 100 символов.

Результат

Для каждого из N сравнений выведите YES или NO, в зависимости от того, удовлетворяет строка шаблону или нет.

Пример

исходные данные

результат

15
'abcde' like 'a'
'abcde' like 'a%'
'abcde' like '%a'
'abcde' like 'b'
'abcde' like 'b%'
'abcde' like '%b'
'25%' like '_5[%]'
'_52' like '[_]5%'
'ab' like 'a[a-cdf]'
'ad' like 'a[a-cdf]'
'ab' like 'a[-acdf]'
'a-' like 'a[-acdf]'
'[]' like '[[]]'
'''''' like '_'''
'U' like '[^a-zA-Z0-9]'

NO
YES
NO
NO
NO
NO
YES
YES
YES
YES
NO
YES
YES
YES
NO

Автор задачи: Павел Атнашев
Источник задачи: Third USU personal programming contest, Ekaterinburg, Russia, February 16, 2002