Pattern Matching

Time Limit: 1 sec

 

The Problem

Develop a program that, given a pattern and a string, determines whether or not the string matches the pattern. The given string will be composed entirely of lower case letters (i.e., any among a, b, ..., z). The pattern will be composed of lower case letters along with the full stop (.) and asterisk (*) symbols. The symbols in a pattern act as follows:

 

a. A letter not followed by an asterisk is matched by one occurrence of that letter.

b. A full stop not followed by an asterisk is matched by one occurrence of any letter.

c. A letter followed by an asterisk is matched by zero or more occurrences of that letter.

d. A full stop followed by an asterisk is matched by any string of zero or more letters.

 

The Input

The first line of input contains a positive integer number T < 50, where T denotes the number of test cases. Next T lines contains two strings P and S separated by a space, where P is the pattern and S is the string (0 <= |P|, |S| < 1000). Each pattern P and each string S is enclosed between a pair of hash sign (#).

 

The Output

For each test case you have to print “YES” or “NO” in a seperate line. If string matches the pattern then print “YES” otherwise “NO”.

 

Sample Input

2

#.*baa*b# #bab#

#ba# #ca#

 

Sample Output

YES

NO

 

 

 

Inter University Programming Contest - Summer 2019 [BGC Trust University Bangladesh]

Problem Setter: Shahin ShamS