#P1816. Wild Words

Wild Words

描述
一个单词是一个由小写字母组成的字符串。一个单词模式是一个由小写字母、?* 组成的字符串。在模式中,? 匹配任意单个小写字母,* 匹配零个或多个小写字母。

现在有许多单词模式和一些单词。在每个单词上,你的任务是判断哪些模式与它匹配。

输入
输入的第一行包含两个整数 NN0<N1000000 < N \leq 100000)和 MM0<M1000 < M \leq 100),表示单词模式的数量和单词的数量。接下来的 NN 行每行包含一个单词模式,假设所有模式的编号从 00N1N-1。之后的 MM 行每行包含一个单词。

你可以假设模式的长度不会超过 6,单词的长度不会超过 20。

输出
对于每个单词,按递增顺序打印所有匹配的模式的编号,每个编号后面跟一个空格。如果没有任何模式匹配该单词,输出“Not match”。

输入数据 1

5 4
t*
?h*s
??e*
*s
?*e
this
the
an
is

输出数据 1

0 1 3 
0 2 4 
Not match
3

来源
POJ Monthly