Ctrl K

Блоки слов в любом порядке

Сложная
Дана строка text и список blocks из строк **одинаковой** длины (в списке могут быть повторы). Найдите все позиции в text, с которых начинается фрагмент, составленный из всех блоков, записанных подряд в каком-нибудь порядке: каждый блок использован ровно столько раз, сколько он встречается в blocks, и между блоками нет других символов. Верните индексы начала таких фрагментов (нумерация с нуля) в любом порядке.
Пример 1
text="catdogcatcow", blocks=["cat", "dog"] → [0, 3]

С позиции 0 читается catdog, с позиции 3 — dogcat: оба склеены из cat и dog. С позиции 6 идёт catcow, это не подходит.

Пример 2
text="abbaab", blocks=["ab", "ba"] → [0, 2]

abba (позиция 0) и baab (позиция 2) подходят, а bbaa с позиции 1 — нет.

Пример 3
text="aaaa", blocks=["aa", "aa", "aa"] → []

Три блока по две буквы — это 6 символов, а строка короче.

Ограничения
  • 1 ≤ len(text) ≤ 10⁴
  • 1 ≤ len(blocks) ≤ 5000
  • 1 ≤ len(blocks[i]) ≤ 30, все блоки одной длины
  • text и blocks[i] состоят из строчных латинских букв
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиКратчайший отрезок со всеми буквами СложнаяСамый длинный чистый фрагмент СложнаяРовные отрезки без скачков СложнаяПодстроки, вмещающие набор букв: большие данные СложнаяБуква набирает k повторов: большие данные Сложная
загружаем Python…
Вход
text="catdogcatcow", blocks=["cat", "dog"]
Ожидается
[0, 3]

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