Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
> Прежде всего ты сирен повстречаешь, которые пеньем\
Всех обольщают людей, какой бы ни встретился с ними.\
Кто, по незнанью приблизившись к ним, их голос услышит,\
Тот не вернется домой никогда.\
`\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ` Одиссея, песнь 12
Корабль Одиссея проплывает мимо скал, населенных сладкоголосыми сиренами. Сирены непрерывно
и бесконечно поют свою песню, раз за разом повторяя одну и ту же последовательность нот длины `N`.
Несколько звучащих подряд нот могут образовать заклинание длины `M`, которое лишает разума любого слушателя на время `T`.
То есть, если ноты с номерами от `i-M+1` до `i` включительно образуют заклинание, то во время звучания
следующих `T` нот (с `i+1` по `i+T` включительно) все гребцы Одиссея бросают весла и корабль не двигается.
После окончания действия заклинания гребцы сразу же (в начале звучания ноты с номером `i+T+1`) приходят в себя и возвращаются к работе,
если только не попадут под действие заклинание снова. Если в момент срабатывания заклинания гребцы уже лишены разума, заклинание
все равно действует (см. пример). Чтобы пересечь опасный участок моря, на котором слышно пение сирен, нужно проработать
веслами в общей сложности в течение времени `L`. Определите, сколько времени на это потребуется кораблю Одиссея.
В первой строке ввода указано 4 натуральных числа: число нот в песне `N`, число нот в заклинании `M` (`1<=N,M<=10^5`),
время действия заклинания `T` (`1<=T<=10^10`) и необходимое время гребли L (`1<=L<=10^10`). Время измеряется
в единицах, равных продолжительности звучания одной ноты.
Вторая строка содержит `N` строчных латинских букв - ноты, содержащиеся в песне сирен.
Третья строка содержит `M` строчных латинских букв - ноты, образующие заклинание.
Выведите единственное целое число -- время, которое потребуется кораблю для преодоления опасного участка. Если
корабль попадет в плен к сиренам навечно, выведите -1.
```sample Пример ввода 1
3 4 2 8
aab
abaa
```
```sample Пример вывода 1
14
```
```sample Пример ввода 2
3 1 4 4
abc
c
```
```sample Пример вывода 2
-1
```
Пояснение к примеру 1. Песня будет звучать так: aabaabaabaabaab...
Заклинание впервые сработает в конце 5-й ноты (т.к. символы со 2-го по 5-й равны "abaa"), поэтому
в течение 6-й и 7-й нот гребцы бездействуют. Затем на 8-й ноте гребцы снова гребут, а на 9-й и 10-й бездействуют (из-за того, что ноты с 5-й по 8-ую вновь равны "abaa"). Затем заклинание будет срабатывать в конце 11-ой, 14-ой и т.д. нот.
Гребцы будут грести в следующие ноты: 1, 2, 3, 4, 5, 8, 11, 14. В конце 14-ой ноты накопленная продолжительность гребли достигает 8, и корабль покидает опасный участок.
Начало
Рабочее место участника
Поиск подстроки, префикс-функция, z-функция