Задача №111993. Газета
«Sam Topge был найден мертвым в своей квартире» — большими буквами было написано на обложке местной газетки, которую так любил читать дома по вечерам Мистер Холмс. "Уже четвертый иностранец за месяц", — грустно подумал он. — "Завтра будет много работы". Холмс выключил свет и, повалившись на кровать от усталости, сладко уснул.
Мистер Холмс работает детективом, и, конечно же, именно ему поручено исследовать дело об этом серийном убийце. "Никаких улик, никаких следов борьбы. Как тут вообще что-то можно найти? Даже медики не могут определить, как они умерли", — думал он, сидя на работе. Никакой зацепки не было, можно было надеяться только на чудо.
Проведя весь день на работе, безуспешно пытаясь найти хоть какую-нибудь маленькую улику, мистер Холмс, грустный и уставший, потопал домой. Шел он, как обычно, через лавку с газетами, чтобы купить свежий выпуск его любимой газеты. "Здравствуйте, Чед, мне как обычно" — "Вы выглядите неважно, мистер Холмс. Возьмите отпуск, отдохните. Вот, держите газету". "Спасибо за совет", — ответил Холмс, взял газету и побрел домой.
Поужинав, Холмс сел на свое любимое кресло перед камином, и, достав свою любимую газету, расслабился после тяжелого рабочего дня. "Что-то не так", — подумал он, увидев в своей привычной газете другой шрифт и формат текста. Он почувствовал, что и бумага недостаточно мягкая, как полагается его любимой газете. "Что мне подсунули? Это не та газета!" — снова напрягся Холмс. "«Stopgame». Ну что за заголовок? Что это за странная газета? Ненавижу этот день!". Холмс бросил газету в камин, и отправился спать.
Под утро у детектива не вылетало из головы название газеты. "Stopgame... Stopgame... Как будто я уже недавно это где-то видел..." — думал он, идя на работу.
"Точно!" — громко воскликнул Холмс в полицейском участке, чем привлек внимание всех вокруг. Детектив быстро взял какую-то бумажку, написал на ней «Stopgame», порвал ее на несколько частей и сложил их. "Sam Topge", — обрадовался Холмс. — "Но почему? Может, это случайность?". Детектив выскочил из участка и побежал к продавцу газет.
"Вы мне вчера дали не ту газету!" — запыхавшись, сказал Холмс — "Дайте мне такую же, пожалуйста, на ней написано «Stopgame»". Чед хотел было извиниться, но, видя сияющие глаза Холмса, понял, что, кажется, он ему только помог. Чед протянул Холмсу газету, тот выхватил ее из рук и принялся спешно читать ее.
"Какая-то статья про зависимых от компьютерных игр детей... Ничего интересного. Может, просто совпадение?" — подумал Холмс, взял газету, и пошел обратно в офис.
Перечитав газету, Холмс не нашел ничего интересного. Посмотрел данные о самой газете — уже более десяти лет она продается в ближайших районах. Потеряв надежду, Холмс отбросил газету на дальний край своего стола и принялся снова искать зацепки.
Прошло еще 3 дня. Холмс потерян. "Их убивает что-то изнутри. Что-то просто отнимает у них жизнь. И уже довольно скоро появится новая жертва. Все они умирают вечером, все во вторник. А завтра вторник. Нужно срочно что-то делать". Холмс увидел отброшенную газету, и его посетила одна гениальная мысль.
Холмс рванул в дома, где жили иностранцы. У каждого из них он нашел эту газету последнего выпуска, которую еще могли купить убитые. "Бинго! Зацепка!" — возрадовался Холмс. — "Имя каждого из убитых — подпоследовательность букв из заголовка газеты!". "Кто же это мог быть? Как эти имена так удивительно могут образовывать другие слова?". Холмс решил проверить сотрудников редакции газеты. Оказалось, главный по заголовкам в последнее время работает на дому. "Мы его видели за странным делом", — говорят сотрудники, — "он нарезал бумагу и клеил в странную кожаную потертую тетрадку".
Холмс работал всю ночь напролет. Он выяснил, кто этот сотрудник, и узнал, что всех этих иностранцев он знал — они вместе воевали. Под утро Холмс решил навестить его. Но не тут-то было: его не было дома.
Газета выходила каждый вторник утром. Холмс решил сходить за ней. Взяв газету, он передал ее своему напарнику, а сам решил выяснить, кто может быть следующей жертвой. Холмс, всю ночь провозившись с делом странного сотрудника редакции газеты, быстро справился с этой задачей, после чего раздался громкий звонок телефона Холмса.
"Он в своем доме, делает что-то странное", — сообщили ему коллеги. И тут Холмс понял, что у него совсем мало времени. Но Холмс хочет знать точно, сколько времени убийца потратит на разрезание названия газеты. "Эй, Ватсон, посчитай мне быстро, сколько разрезов ему нужно сделать, чтобы собрать имя и фамилию убитого?" Сегодня Ватсон — это вы. Помогите Холмсу определить минимальное количество времени, которое уйдет у убийцы на разрезание названия газеты.
Длину строки q обозначим как |q| (|abac| = 4, |sam| = 3). Во входном файле содержатся 3 строки s, t1, t2 (|s| = |t1| + |t2|, 1 ≤ |t1|, |t2| ≤ 1 000). Все строки содержат только маленькие латинские буквы.
Подстрокой p[l, r] назовем строку, состоящую из символов pl, pl + 1, ..., pr - 1, pr, где pi — i-тый символ строки p («cde» является подстрокой строки «abcdef», «bcf» — не является).
Тогда любую строку p можно представить в виде разбиения на непересекающиеся подстроки p[x0 + 1, x1] + p[x1 + 1, x2] + p[x2 + 1, x3] + ... + p[xn - 1 + 1, xn], где 0 = x0 < x1 < x2 < ... < xn - 1 < xn = |p|. При этом длиной разбиения будем называть количество чисел xi, то есть число n.
В данной задаче требуется найти разбиение строки s такое, чтобы из получившихся подстрок можно было сложить строки t1 и t2, не нарушая порядка, в котором подстроки шли в исходной строке. Например, из строки «adbc» нельзя будет выложить слова «cad» и «b», так как порядок подстрок «ad» и «c» будет нарушен.
Программа должна выдавать на экран одно число — минимально возможную длину такого разбиения, то есть количество разрезов, которые потребуется сделать убийце.
Гарантируется, что существует разбиение строки s хотя бы одним способом, чтобы получились строки t1 и t2.
stopgame
sam
topge
3
ababbaba
abbb
abaa
4
В первом примере из условия строку можно разрезать следующим образом: stopgame 
s|topg|am|e.
Во втором примере: ababbaba ab|abb|a|b|a.