Submeter | Todas submissőes | Melhores | Voltar |
WORDPOW - Word Power |
Farmer John wants to evaluate the quality of the names of his N (1 <= N <= 1000) cows. Each name is a string with no more than 1000 characters, all of which are non-blank.
He has created a set of M (1 <= M <= 100) 'good' strings (no longer than 30 characters and fully non-blank). If the sequence letters of a cow's name contains the letters of a 'good' string in the correct order as a subsequence (i.e., not necessarily all next to each other), the cow's name gets 1 quality point.
All strings is case-insensitive, i.e., capital letters and lower case letters are considered equivalent. For example, the name "Bessie" contains the letters of "Be", "sI", "EE", and "Es" in the correct order, but not "is" or "eB". Help Farmer John determine the number of quality points in each of his cow's names.
Input
- Line 1: Two space-separated integers: N and M
- Lines 2..N+1: Line i+1 contains a string that is the name of the ith cow
- Lines N+2..N+M+1: Line N+i+1 contains the ith good string
Output
- Lines 1..N+1: Line i+1 contains the number of quality points of the ith name
Example
Input: 5 3 Bessie Jonathan Montgomery Alicia Angola se nGo Ont
There are 5 cows, and their names are "Bessie", "Jonathan", "Montgomery", "Alicia", and "Angola". The 3 good strings are "se", "nGo", and "Ont".
Output: 1 1 2 0 1
"Bessie" contains "se", "Jonathan" contains "Ont", "Montgomery" contains both "nGo" and "Ont", Alicia contains none of the good strings, and "Angola" contains "nGo".
Adicionado por: | Wanderley Guimarăes |
Data: | 2008-06-06 |
Tempo limite: | 1s |
Tamanho do fonte: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Linguagem permitida: | ADA95 DOC ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PDF PERL PHP PIKE PS PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE |
Origem: | USACO Open 2008 - Silver |