Step 6 (S-100976)

From Stepik Wiki
Jump to: navigation, search

Step on Stepik: https://stepik.org/lesson/24469/step/6

Вашей программе на вход подаются три строки s, a, b, состоящие из строчных латинских букв.
За одну операцию вы можете заменить все вхождения строки a в строку s на строку b.



Например, = "abab"a"ab"b = "ba", тогда после выполнения одной операции строка перейдет в строку "baba", после выполнения двух и операций – в строку "bbaa", и дальнейшие операции не будут изменять строку s.


Необходимо узнать, после какого минимального количества операций в строке s не останется вхождений строки a, либо же определить, что это невозможно.



Выведите одно число – минимальное число операций, после применения которых в строке s' не останется вхождений 'строки a.

Если после применения любого числа операций в строке s останутся вхождения строки a, выведите Impossible.