T9
Time limit: 20 seconds
Problem
Many of us have experience of writing SMS on a phone.
To type in English words, each digit on the keypad
is associated with some characters, as shown below.
Let us be case-insensitive and assume all characters
are in lower-case.
In the traditional systems,
typing in the i-th character associated with a digit
requires pressing that digit i times.
A new technology called T9 is developed to reduce the
number of key presses required.
According to http://en.wikipedia.org/wiki/T9_(predictive_text):
|
T9, which stands for Text on 9 keys, is a patented[1] predictive text technology for mobile phones, originally developed by Tegic Communications, now part of Nuance Communications[2].
|
Roughly speaking, T9 maintains a dictionary and
changes the pressing requirement to "one press per character":
to type in any character, a user only press the associated digit once.
Hence typing in a character 'e' requires a
single press on digit '3', which is same as typing in 'f'.
Typing in the word "provinci"
requires pressing the sequence "77684624".
T9 is responsible for converting the input sequence
into a word. To simplify our discussion, we assume T9 displays
all words in the dictionary whose press sequence is same
as the input.
Input
The first line is an integer 1 <= n <= 500,000.
It is followed by n lines,
each containing a single word in the dictionary.
Each word has at most 60 characters and no space.
All characters are in lower-case.
The words are given in alphabetical order.
Then there is a line with an integer 1<= q <= 10,000.
It is followed by q lines,
each containing a single press sequence
with digits '2' to '9' only.
Output
For each press sequence, print all the English words in
the input dictionary with the same press sequence,
in alphabetical order and separated by
a single space. If no such word, print "NO MATCHES".
Print on a single line for each press sequence.
Sample Input
4
acm
can
programming
provinci
4
77684624
226
77647266464
6793
Sample output
provinci
acm can
programming
NO MATCHES
Author
Chi-Yung Tse