AUTOMATA - GAME2
Bob is playing Hide and Seek with alphabets and he is amazed by the properties of '?' and '*' in the language. He is given a language 'L'. He has to check whether the given string 'S' is present in the language 'L'. He needs your help. Print "Yes" if S is present in L, else print "No".
Definition for L :
- L consists of 28 characters, a-z and '?' and '*'.
- ? denotes 0 or 1 character(s).
- * denotes 0 or any number of characters.
Example:
- String "adb" is present in language L = {a?b}
- String "adb" is present in language L = {a*b}
- String "ab" is present in language L = {a?*b*}
Input
First line of input consists of T (T<=50). Every test case consists of two strings, first line consists of 'L' and second line consists of 'S'. L consists characters among the 28 characters 'a'-'z', '?', '*' only. S consists of only lower case letters.
Output
Print "Yes" if String 'S' is present in language 'L', else print "No".
Example
Input: 5 a?b acb a?b abbb a*b abbbb a*b asbdfuisdhfsbdfsdfb abb bb Output: Yes No Yes Yes No
hide comments
Rafail Loizou:
2020-11-18 23:43:00
Notice: 10^4 max language size |
|
rising_stark:
2020-04-27 04:22:44
@sachit9_ The solution must be O(n*m) where n and m are lengths of the String S and the language L respectively.
|
|
nadstratosfer:
2020-02-08 23:11:12
Second sample case doesn't make sense: a?b can match ab and abb, both present in abbb. Why is the answer "No" then?
|
|
sachit9_:
2020-02-08 14:53:39
can anyone tell, till what constarints code will give ac ? |
|
techobist:
2019-01-31 18:40:14
how "bb" is not contained in "abb"?
|
|
[Rampage] Blue.Mary:
2016-08-22 05:10:29
What's the maximum length of the input string? Will the input consist of empty lines?
|
Added by: | [[soup_boy]] |
Date: | 2013-04-09 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: MAWK BC NCSHARP COFFEE DART FORTH GOSU JULIA KTLN OCT PROLOG PYPY3 R RACKET SQLITE SWIFT UNLAMBDA |