This page is still under construction.

Parts of this page are still being built. What you see may change.

Ransom Note

Time limit1sMemory limit128 MB

Summary
Given a target note and a newspaper text, find the minimum number of contiguous clips (letters and spaces only, case-insensitive, reusable) needed to paste the note.
Level

Hard8 of 10

Topics
Dynamic programming, String, String matching, Implementation
Solved
No attempts yet

Problem

Gilbert Bates, the magnate of aluminum siding, doors, and windows, has been kidnapped, and you must help the kidnappers put together a ransom note. Your raw materials are the text of a newspaper and the text of the ransom note. The note is assembled by clipping letters -- or runs of letters, possibly including spaces -- out of the newspaper and pasting them onto a blank sheet of paper to spell out the note. Determine the minimum number of clippings that must be cut out and pasted to form the note. Between each pair of adjacent words in the note, either one clipping must itself contain the separating space, or a boundary between two clippings must fall there so that the blank background shows through as the space.

Input

The first line is the text of the note: a single line shorter than 2 0482\,048 characters, written in lowercase with no punctuation (its words are separated by single spaces). The following lines are the text of the newspaper, which mixes uppercase and lowercase letters, punctuation, and newlines; it is shorter than 9 2179\,217 characters. Case is ignored when matching (aS IN aNY stANDard RAnsoM nOTE), and punctuation and newlines can never be clipped -- a clipping is always a contiguous run of letters and spaces taken from the newspaper. The kidnappers own many identical copies of the newspaper, so the same or overlapping text may be clipped as many times as needed. Every letter of the alphabet occurs at least once in the newspaper.

In at least 60% of the tests, the newspaper is shorter than 2 0482\,048 characters.

Output

Print a single integer: the minimum number of clippings that must be cut from the newspaper to assemble the note.

Examples3

  1. Example 1

    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.
    Expected output
    19

  2. Example 2

    Input
    cat
concatenate the vector before the match.
    Expected output
    1

  3. Example 3

    Input
    to be
to be or not to be, that is the question.
    Expected output
    1