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.
So, this would mean that both S and L can be upto 10^4 at max.

Also, bit of advice, try solving it in O(m) space.

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?

=(Francky)=> if word a?b = abbb, then ? = bb which is forbidden. ? is for 0 or 1 char, not two. "Present in a language" is not "is substring", it is rather "in the set of words". A language is a set of words, eg : language {a?b} = {ab, aab, abb, acb, adb ..., azb}. Description is misleading a bit with the confusion between L and its definition. A language is a set of words whose letters are in [a-z], and definition of language is a string made of [a-z*?].

Last edit: 2020-02-09 13:35:27
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?

Edit: My ACed C program assumes length <= 1000, no empty lines.

Last edit: 2016-08-22 05:35:24

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