当前位置:码农谷 > 算法与程序 > POJ 1432 Decoding Morse Sequences:题目解答源码

POJ 1432 Decoding Morse Sequences:题目解答源码

所属学科:C语言 - 指针 难度: 关注度:85

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.

输入描述

The first line of the input contains exactly one positive integer d equal to the number of data sets, 1
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

输出描述

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.

程序源码

完整的源代码如下:

#include "stdio.h"
#include"stdlib.h"
#include "string.h"
#include "string"
#include "queue"
#include "algorithm"
#include "vector"
#include"stack"
#include "list"
#include "iostream"
#include "map"
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{

关注微信,获得更多免费资源
关于我们   |   免责声明   |   联系我们   |   网站地图   |   HR交流群   |   学生交流群   |   教师交流群

码农谷   版权所有 © 2015-2017   湘ICP备16018319号-1