5. Магическая подстрока

Не решаласьСложная

Андрей обожает загадки, особенно те, которые можно разгадать при помощи программирования. На днях коллега озадачил его нахождением «магических» строк. Одна строка считается «магической» по отношению к другой, если они равны по длине и обе состоят из одних и тех же букв, за исключением одной буквы в каждой из строк.​

Для данного текста $T$ и строки $S$, требуется найти существует ли в тексте $T$ «магическая» по отношению к строке $S$ подстрока. В качестве ответа верните индекс первой такой подстроки или $-1$, если такой подстроки не существует.​

Формат ввода

В первой строке входных данных находится строка $T$ - текст.

Во второй строке входных данных находится строка $S$ - строка.

Ограничения

$0 \le T.length \text{\textless} 10^8\newline$ $0 \le S.length \text{\textless} 10^8\newline$

Строки $T$ и $S$ состоят из букв английского алфавита в нижнем регистре.

Формат вывода

Индекс с которого начинается «магическая» подстрока.

Выведите наименьший из индексов, если текст содержит несколько «магических» подстрок.

Выведите $−1$, если текст не содержит «магических» подстрок.

Примечание

Объяснение к примеру 1:

Подстрока $cddc$ является «магической» для строки $ccde$, исключенные буквы - $d$ в подстроке текста $T$ и $e$ в строке $S$.

Объяснение к примеру 2:

Подстрока $abcd$ является анаграммой для строки $dcba$, различных букв не существует.

Ограничения

Ограничение времени

10 с

Ограничение памяти

250 МБ

Пример 1

Ввод
abcddc
ccde
Вывод
2

Пример 2

Ввод
abcd
dcba
Вывод
-1

Пример 3

Ввод
abcd
abef
Вывод
-1

Теги

Нужно войти, чтобы отправить решение.Войти