Ctrl K

Кратчайшее совпадение с шаблоном из двух звёздочек

Сложная
Даны строка text и шаблон pattern. Шаблон состоит из строчных латинских букв и ровно двух символов *, причём начинается с буквы. Каждая * заменяет любую последовательность символов, в том числе пустую; буквы шаблона должны совпасть буквально. Найдите самую короткую подстроку (непрерывный фрагмент) text, которая целиком подходит под шаблон, и верните её длину. Если такой подстроки нет, верните -1.
Пример 1
text="xabyyabzcab", pattern="ab*ab*c" → 8

Подходит фрагмент abyyabzc: ab, пропуск yy, ab, пропуск z, c. Его длина 8, короче не найти.

Пример 2
text="rotor", pattern="o**o" → 3

Обе звёздочки могут остаться пустыми: подходит oto длины 3.

Пример 3
text="pattern", pattern="t*e*a" → -1

После t и e буквы a в тексте нет.

Ограничения
  • 1 ≤ len(text) ≤ 10⁵
  • 2 ≤ len(pattern) ≤ 10⁵
  • text состоит из строчных латинских букв
  • pattern состоит из строчных латинских букв и ровно двух *
  • Первый символ pattern — буква
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСлово рядом с якорем СложнаяЯкорь рядом с напарником СредняяХвосты, повторяющие начало СложнаяДешёвый вырез до подпоследовательности СложнаяФраза из начал слов: длинная версия Сложная
загружаем Python…
Вход
text="xabyyabzcab", pattern="ab*ab*c"
Ожидается
8

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 19 тестов на сервере, включая скрытые.