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.
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.
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.
5 the a cow there re 3 therecow acowrethe zyzzy
there cow a cow re the ***zyzzy