| Seti | Solution | Tests |
It seems that, finally, the searchers of extra-terrestrial life discovered something! During the SETI@home project a sequence has been isolated that could represent a signal from other forms of intelligent life. As a result, the SETI@ONI project is proposing to verify if this signal really comes from aliens or if it comes from kids drinking Fanta.
TASK
For convenience, the part of the signal that needs to be analyzed is at your disposal as a sequence of letters from the Latin alphabet. At your disposal there is also a dictionary containing extra-terrestrial words, encoded in the same way. Your task is to count how many times each word appears in the possible alien message. Using this information, the linguists can translate the message.
INPUT FORMAT
On the first line of the SETI.IN input file is written N, the number of lines of the message. Each of the following N lines have exactly 64 letters of the Latin alphabet followed by a newline character. The message to be analyzed, formed by 64*N letters, is obtained by concatenating these lines.
On the first line of the other input file, DIC.IN, is written M, the number of words that are in the dictionary. Each of the following M lines contains a word from the dictionary, represented as a sequence that has at least 1 (one) letter and no more than 16. The words aren’t necessarily distinct.
OUTPUT FORMAT
The output file SETI.OUT will contain exactly M lines. On the ith line will be written the number of appearances, in the alien message, of the word that has the ith number in the dictionary. The number of appearances will never be bigger than 65 535. Any appearance of a word must be counted, even if it overlaps other appearances. There will be made the difference between small and capital letters.
CONSTRAINTS:
Example:
SETI.IN
2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaBaba
babaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaBaB
DIC.IN
3
b
bab
b
SETI.OUT
3
2
3
TIME LIMIT: 1 second/test