2000 Canadian Computing Competition, Stage 2

Day 1, Problem 2: Ransom Note

Gilbert Bates, the magnate of aluminum siding, doors, and windows, has been kidnapped. You are to help the perpetrators produce a ransom note. Your raw materials are the text of a newspaper and the text of the ransom note. The ransom note is to be produced by clipping letters or strings of letters (and possibly spaces) from the newspaper and pasting them onto a blank sheet of paper to form the note. Your job is to determine the minimum number of pieces of paper that must be clipped and pasted to form the note. Between each pair of words in the note, either the clipping must contain a space or a boundary between clippings must occur (so that the blank background shows through).

Input

The input file consists of the text of the note followed by the text of the newspaper.
The text of the note is a single line, less than 2KB in length, in lowercase with no punctuation.
The text of the newspaper is in upper and lower case with punctuation and newlines mixed in. Case may be ignored (aS IN aNY stANDard RAnsoM nOTE) and punctuation and newlines should not be clipped.
The kidnappers have acquired a large number of copies of the same newspaper, so that the same or overlapping text may be clipped as many times as necessary. Every letter of the alphabet occurs at least once in the newspaper. The newspaper is smaller than 9KB in length. In at least 60% of the test cases the newspaper will be smaller than 2KB. An inefficient algorithm will probably exceed the time limit (about 15 seconds) when solving the larger cases.

Output

Print the minimum number of clippings followed by the clippings, one per line, in the correct order to compose the note. The case of the newspaper text should be preserved.

Sample Input

drop the price on new thermopanes now or else
Rain Users Guide (by J.Z.)
While "rain" was intended to be a general purpose tool, at the time of
writing the primary goal was to study one particular software system.
As a result, some steps that are only done once (such as extracting
information from the program under study) are done using cumbersome
ad-hoc techniques that require significant manual intervention.  While
"rain" can be used on arbitrary programs, more development work needs
to be done before this is a convenient process.

Sample Output

19
d
ro
p
the pri
ce
on
ne
w
the
rm
op
an
es
n
o
W
or
el
se

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 19, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...