← 返回 google 的题目列表Morse Code Decoding (count or enumerate all decodings)
类型：online_judge
Problem: Morse Code Decoding (possibly multiple decodings)
You are given a string s consisting only of . and -, representing continuous Morse code with no delimiters between letters. A mapping table provides Morse codes for uppercase letters A-Z (one-to-one, each code is a non-empty string of ./-).
A decoding is obtained by splitting s into segments such that every segment matches exactly one letter’s Morse code. Since there are no delimiters, multiple splits (thus multiple decodings) may exist.
Task
Write a program that outputs:
The number of valid decodings.
If the number is > 0, output the lexicographically smallest up to K decoded strings, where K = 10.
Input (stdin)
Line 1: Morse string s
Line 2: integer m (number of mappings)
Next m lines: <LETTER> <CODE> (e.g., A .-)
Output (stdout)
Line 1: number of decodings
Next up to 10 lines: the first 10 decodings in lexicographic order
Constraints
1 <= |s| <= 1e5
m <= 26
Total length of all codes <= 1e4
The count can be huge; output it modulo 1_000_000_007.
Example
Input:
...-
4
A .-
B -...
E .
V ...-
Output:
2
EV
V
Example
Input
...-
4
A .-
B -...
E .
V ...-
Output
2
EV
V