505. Prefixes and suffixes
Time limit per test: 0.75
second(s)
Memory limit: 262144
kilobytes
input: standard
output: standard
Andrew has just made a breakthrough in biology: he realized that
most of genome's characteristics are determined by the absence
or presence of certain prefixes and suffixes. So he needs to quickly
test large arrays of genomes for that.
More formally, we represent the genome as a string of lowercase English
letters. We are given several genomes, and need to answer the following
type of question: how many genomes from the given set have the given
string
p as prefix
the given string
s as suffix.
Input
The first line of the input file contains an integer
n —
the number of genomes.
The next
n lines contain a nonempty
string of lowercase
English letters each, representing the given genomes. The total length
of all given genomes doesn't exceed
.
The next line contains an integer
m — the number of questions to answer.
The next
m lines contain two nonempty strings of lowercase English letters
each, the
first denoting the prefix and the second denoting the suffix. The prefix and
suffix are separated with a single space. The total length of all given
prefixes plus the total length of all given suffixes doesn't exceed
.
Output
Output
m integers one per line.
ith output line should contain the
number of genomes that have
ith given prefix and
ith given suffix.
Example(s)
sample input

sample output

3
aaaaa
abacabaa
avtobus
6
a a
a aa
aa a
aaaaa aaaa
abac caba
abac a

2
2
1
1
0
1
