MORSE - Decoding Morse Sequences

Before the digital age, the most common "binary" code for radio communication was the Morse code. In Morse code, symbols are encoded as sequences of short and long pulses (called dots and dashes respectively). The following table reproduces the Morse code for the alphabet, where dots and dashes are represented as ASCII characters "." and "-":

A .-   B -... C -.-. D -.. 
E .    F ..-. G --.  H .... 
I ..   J .--- K -.-  L .-.. 
M --   N -.   O ---  P .--. 
Q --.- R .-.  S ...  T - 
U ..-  V ...- W .--  X -..- 
Y -.-- Z --..

Notice that in the absence of pauses between letters there might be multiple interpretations of a Morse sequence. For example, the sequence -.-..-- could be decoded both as CAT or NXT (among others). A human Morse operator would use other context information (such as a language dictionary) to decide the appropriate decoding. But even provided with such dictionary one can obtain multiple phrases from a single Morse sequence.

Task

Write a program that:

  • reads a Morse sequence and a list of words (a dictionary),
  • computes the number of distinct phrases that can be obtained from the given Morse sequence using words from the dictionary,
  • writes the result.

Notice that we are interested in full matches, i.e. the complete Morse sequence must be matched to words in the dictionary.

Input

The first line of the input contains exactly one positive integer d equal to the number of data sets, 1 <= d <= 20. The data sets follow.

The first line of each data set contains a Morse sequence - a nonempty sequence of at most 10000 characters "." and "-" with no spaces in between.

The second line contains exactly one integer n, 1 <= n <= 10000, equal to the number of words in a dictionary. Each of the following n lines contains one dictionary word - a nonempty sequence of at most 20 capital letters from "A" to "Z". No word occurs in the dictionary more than once.

Output

The output should consist of exactly d lines, one line for each data set. Line i should contain one integer equal to the number of distinct phrases into which the Morse sequence from the i-th data set can be parsed. You may assume that this number is at most 2*109 for every single data set.

Example

Sample input:
1 
.---.--.-.-.-.---...-.---. 
6 
AT 
TACK 
TICK 
ATTACK 
DAWN 
DUSK 

Sample output:
2 

Added by:adrian
Date:2004-07-02
Time limit:7s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:ACM Central European Programming Contest, Warsaw 2001

hide comments
2020-09-13 13:05:22
Solution without TRIE also passing.
2019-04-02 19:27:41
great problem, the hint is not to read the comments because it will spoil the solution :}
2019-03-27 16:12:30
wow the quality of this problem is never ceasing to amaze me ^_^
2019-01-30 22:42:34
cpp14-clang accepted
but
cpp14-gcc6.3 wrong answer...

For some pequliar reason (slow browser update ?) only when cpp14-gcc selected, I had to wait quite some seconds before I should paste the code otherwise it compiled the absolute void!!!


Last edit: 2019-02-01 00:11:21
2019-01-11 17:49:28
Here is my code: <snip>
You can look through <3

Last edit: 2022-10-11 16:38:37
2017-02-25 08:50:00
took whole day to just figure out that same word can appear more than ones and these same words will be considered different while calculating number of ways.
for example
1
.
2
E
E
No of ways will be 2.
2016-02-07 16:27:53
it seems something is wrong :|
the sequence(.---.--.-.-.-.---...-.---.) can contain 4 words =>

AT: .--
TACK: -.--.-.-.-
ATTACK: .---.--.-.-.-
DAWN: -...-.---.
-------------------------------------------------------------------
and if no character of sequence should be used more than once, then the sequence is composed of this three words:

ATTACK: .---.--.-.-.-
AT: .--
DAWN: -...-.---.
------------------------------------------------------------
it means the output should be 4 or 3, but as you can see in the example, it's 2 !
someone please explain this example for me :((
2014-11-06 18:52:43 Jose Sanchez
Warning: the words can appear more than once!
@azalathemad: you are right :)
2014-04-16 19:09:29 harsh
nice question.

Last edit: 2014-04-17 15:04:07
2013-12-23 10:57:59 Dewan Mahmud Raihan
really nice problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.