Decoding Morse Sequences

Description

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 "-":

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 which for each data set:

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 10 000 characters "." and "-" with no spaces in between.

The second line contains exactly one integer n, 1 <= n <= 10 000, 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 * 10^9 for every single data set.
Sample Input

1
.---.--.-.-.-.---...-.---.
6
AT
TACK
TICK
ATTACK
DAWN
DUSK
Sample Output

2

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

2
12306抢票打包exe报错json.decoder.JSONDecodeError: Expecting value: line 1 column 1 (char 0)
1
使用狮子对字符串编码的问题,输出需要多少解码?采用C语言编程
1
C++用哈弗曼编码实现压缩,编码文件比原文件大是怎么回事,怎么能实现压缩,代码如下,求修改
0
Qt调用MATLAB程序就会发生错误自动退出界面,会去找pdb文件,要怎么解决,求各位大神解答,拜托拜托!!!
1
求助:pyinstaller3.5 打包 WARNING: Cannot read QLibraryInfo..... json.decoder.JSONDecodeError..
0
信息论提到的熵的概念的一种计算的方式,怎么采用C程序编写设计代码的思想合理实现?
0
十六进制数据的分析的一个问题,怎么采用C程序的代码的编写技术思想去实现呢?
1
springcloud eureka在tomcat中运行 无法访问eureka首页
0
网络通讯协议的buffer分析问题,怎么采用C程序语言的编写代码的技术方法去实现分析?
0
SSL_connect failed,err code=-155;做ssl连接aws服务器的时候,出现一直ssl_connect failed。
1
tx-lcn分布式事务客户端无法启动
0
字符串特定解码的一个高效的算法的问题,怎么使用C语言的程序的设计的方式来实现的呢
1
HM代码在深度学习应用调试过程中出现如下的问题,有人遇到过吗??
0
Entropy,商数的计算算法
0
Protocol Buffers
1
Decode the Strings 字符串的问题
1
springboot项目启动后自动结束 报的错如下,请路过的大神不吝赐教
1
解码出的pcm有问题,我要怎么修改增加代码?
0
pydub无法打开wav文件
1
我把hive-site.xml放进spark/conf/里后报了一堆警告,怎么处理,不处理有影响吗?