O comando glob, nome curto para global, era um programa presente nas primeiras versões do Unix. Sua função era fazer expansão de uma expressão e passar para outro programa todos os arquivos que casavam com aquele expressão. Como exemplo, a expressão '*' casa com o nome de todos os arquivos, então pode literalmente significar "todos os arquivos". Nos dias atuais, o glob foi englobado por funções de biblioteca, e faz parte da habilidade padrão dos shells.
Porém, Zaphod não trabalha com arquivos no seu dia a dia. Seu trabalho está ligado a criação de um Sistema Gerenciamento de Banco de Dados (SGBD) chamado MyPostcle. Nesse banco de dados, é usado uma linguagem de consulta Só Que Louco (SQL), que permite consultas nesse estilo:
SELECIONE nome, salario DE funcionario ONDE nome EH TIPO 'Zaphod B%' E salario EH TIPO '[1-9]__[34][^9][^8]'
Agora, está na fase do projeto de implementar a funcionalidade do TIPO que é extremamente parecida com os globs do Unix. Ao invés de usar '*' e '?', a sintaxe é um pouco diferente:
O Zadoph fez um algoritmo, mas ele não passou em todos os testes do SGBD. Desesperado, ele agora está recorrendo a você para ajudá-lo, você consegue implementar a funcionalidade de TIPO da linguagem Só Que Louco?
Na primeira linha se encontra um inteiro $$$N$$$ $$$(1 \le N \le 100)$$$, o tamanho do padrão TIPO. Na próxima linha, se encontra o padrão de tamanho $$$N$$$ que é composto de caracteres ASCII de espaço, alfabeto latino maiúsculo e minúsculo, números, '[', ']', '^', '-', '%' e '_'.
É garantido que depois de '[', opcionalmente existe um '^', e sempre existe um conjunto de caracteres não especiais que podem ser caracteres isolados ou intervalos 'A-Z' que tem extremidades pertencentes ao mesmo grupo (maiúsculas com maiúsculas, minúsculas com minúsculas, números com números, espaço com espaço), e finalmente é sempre finalizado por ']'. Os caracteres '[', ']', '-' e '^' não são usados fora deste contexto.
Na linha seguinte, se encontra um inteiro $$$Q$$$ $$$(1 \le Q \le 10^3)$$$, a quantidade de linhas que serão testadas. Nas $$$Q$$$ linhas seguintes, se encontra um inteiro $$$M$$$ $$$(1 \le M \le 100)$$$ que determina o tamanho do texto a ser testado, um espaço, e o texto a ser testado (que não possui espaços no começo ou no final). O texto possui apenas caracteres de espaço, do alfabeto latino maiúsculo e minúsculos e números.
Imprima todos as linhas que casaram com o padrão na ordem que foram dadas na entrada.
10 Z%aph_d B% 11 17 Zaphod Beeblebrox 20 Ziayphad Bittersweet 21 Ziyaphad Betelgeusian 21 Tricia Marie McMillan 20 Zaphod Beeblebrox II 12 Ford Prefect 23 Zetaphod Beeblebrox III 21 Z123aphad Bittersweet 18 Arthur Philip Dent 20 Zetaphad Bittersweet 21 Z123phad Betelgeusian
Zaphod Beeblebrox Ziyaphad Betelgeusian Zaphod Beeblebrox II Zetaphod Beeblebrox III Z123aphad Bittersweet Zetaphad Bittersweet
19 [1-9]__[34][^9][^8] 8 6 100387 6 100487 6 100388 6 900387 7 9003387 6 a03387 6 103487 6 103587
100387 100487 900387 103487