## CCO '98 P5 - Text Segmentation

View as PDF

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, , indicating the number of words in it, followed by the words, one per line. Following the dictionary is another integer, , and lines of text with no spaces.

No line will be longer than characters. The input contains only lowercase letters. No word in the dictionary exceeds 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

5
the
a
cow
there
re
3
therecow
acowrethe
zyzzy

#### Sample Output

there cow
a cow re the
***zyzzy