CCO '98 P5 - Text Segmentation

View as PDF

Submit solution

Points: 10
Time limit: 2.0s
Memory limit: 64M

Problem type
Canadian Computing Competition: 1998 Stage 2, Day 2, Problem 2

In a word processing accident, all the spaces were removed from a file containing lines of English text. Your job is to replace the spaces in the text.

Input Specification

Your input consists of two parts: a dictionary, and a number of lines of text with no spaces. The dictionary is preceded by an integer, n < 1000, indicating the number of words in it, followed by the words, one per line. Following the dictionary is another integer, m < 1000, and m lines of text with no spaces.

No line will be longer than 100 characters. The input contains only lowercase letters. No word in the dictionary exceeds 20 letters.

Output Specification

Insert spaces into each line so that it is composed of a sequence of words from the dictionary. If there is more than one way to break the line into words, output the solution with the fewest words (or one of the solutions if there are many). If there is no way to break the line into words, print *** followed by the line with no spaces.

Sample Input


Sample Output

there cow
a cow re the


There are no comments at the moment.