O alarme de segurança de
uma grande loja tem a função de detectar os códigos de identificação dos produtos
que saem da loja. Se o código pertencer a um produto que não foi pago, o som do
alarme avisa os seguranças.
Numa época de grande movimento, o alarme avariou. Em vez de detectar os códigos com precisão, passou a registá-los com erro:
1) Regista o código com um qualquer caracter em falta 2) Regista o código com um caracter a mais numa posição qualquer 3) Regista o código mas altera um dos caracteres por outro
Se o código original fosse sapato, um exemplo para cada situação seria:
1) sapao 2) sapatos 3) sapata
Enquanto o alarme não pode ser substituído, pretende-se desenvolver um sistema informático temporário que identifique se algum dos códigos de identificação dos produtos da loja pode corresponder a um código registado pelo sistema de alarme. Nota que o alarme regista sempre os códigos com um, e apenas um dos três possíveis erros atrás descritos.
Tens disponível a lista de códigos de todos os produtos existentes da loja e os códigos registados pelo sensor de alarme. Tens de criar um programa que determine quais dos códigos registados no sensor devem accionar o alarme e avisar os seguranças.
Dado um conjunto de códigos de produtos existentes numa loja e um conjunto de leituras efectuadas pelo sensor de alarme, a tua tarefa é identificar quais as leituras que deveriam accionar o alarme, de acordo com os possíveis erros ocorridos no registo do código lido pelo sensor.
Na primeira linha do input vem um único número inteiro N, representando o número de produtos existentes na loja. Seguem-se exactamente N linhas, cada uma delas representando um dos códigos dos produtos. Estes códigos podem vir por qualquer ordem.
De seguida vem uma linha com um único número inteiro L representando o número de leituras de códigos efectuadas pelo sensor do alarme de segurança da loja. Seguem-se exactamente L linhas, cada uma delas representando um código lido pelo sensor.
Todos os códigos contêm apenas letras minúsculas simples (letras [a-z] sem acentuação).
A primeira linha do output deve apresentar um único inteiro C indicando o número de leituras que deveriam accionar o alarme.
Devem seguir-se exactamente C linhas, cada uma delas representando um dos códigos lidos que deveria accionar o alarme, ou seja, códigos que podem corresponder a produtos existentes na loja. Esta lista deve ser apresentada na mesma ordem de ocorrência no input.
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
1 ≤ N ≤ 10 000 | Número de códigos de identificação da loja | |
1 ≤ L ≤ 10 000 | Número de leituras efectuadas | |
Todos os códigos terão um comprimento inferior ou igual a 20 letras. |
Para um conjunto de casos de teste valendo 50% dos pontos, o número de códigos de identificação e de leituras efectuadas é inferior a 1000.
3 camisola brinquedo sapato 5 sapao sapos camisola sapatos sapata
3 sapao sapatos sapata