Minimum Deletions for Specified ABC Pattern

In many writing exercises and contests, you are asked to mimic a given style. In this problem you are given three phrases A, B, and C – each consisting of one or more words – and a text S (a sequence of words). A work in the specified style has the exact form $$A\;*\;B\;*\;C,$$ which means that after removing some words from S (without changing the order of the remaining words) the final text T should start with the words of A (in order and consecutively), then have an arbitrary sequence of words (possibly empty), then a contiguous block exactly equal to B, then another (possibly empty) block, and finally end with the words of C (again, consecutively). Note that the blocks corresponding to A, B and C must appear as contiguous subsequences in T, although the filler parts represented by '*' may be arbitrary.

Your task is to remove as few words as possible from S so that the remaining text T becomes of the form A * B * C. If no such removal is possible, output -1. Otherwise, output the minimum number of words you must remove.

Input Format:

• The first line contains the phrase A.
• The second line contains the phrase B.
• The third line contains the phrase C.
• The fourth line contains the text S, which is a sequence of words separated by single spaces.

Output Format:

• Output a single integer: the minimum number of words to remove from S so that the remaining words (in order) form a text T which starts with A, then has some (possibly empty) words, then contains B as a contiguous block, then some (possibly empty) words, and ends with C. If it is impossible to obtain such a T, output -1.

Explanation:

Let S be composed of n words. Suppose you can choose three tight occurrences (i.e. choosing the indices for the mandatory blocks without keeping any extra word within each block) for A, B, and C in S. Denote the indices used for the occurrence of A by (a₀, ..., a_|A|-1), for B by (b₀, ..., b_|B|-1), and for C by (c₀, ..., c_|C|-1) such that:

$$a_{|A|-1} < b_{0} \quad \text{and} \quad b_{|B|-1} < c_{0}. $$

Between these mandatory blocks you are allowed to keep all words that lie between the chosen indices. However, you are not allowed to keep any word before the first word of A or after the last word of C because T must start with A and end with C. If the kept words count is maximized, the number of words removed is minimized (namely, removed = n − kept).

Your program should choose the optimal occurrences in S for A, B, and C so that the total number of words kept is as large as possible and then output n minus this number.

inputFormat

The input consists of four lines:

1. Line 1: Phrase A (one or more words separated by spaces).
2. Line 2: Phrase B (one or more words).
3. Line 3: Phrase C (one or more words).
4. Line 4: Text S, a sequence of words separated by spaces.

outputFormat

Output a single integer – the minimum number of words that need to be removed from S so that the remaining text matches the A * B * C pattern. Output -1 if it is impossible.

sample

hello world
good morning
bye friend
greetings hello world and good morning to everyone bye friend

1