Войти Регистрация
Алгоритмы

116. Префиксы выписки из повторов одного цикла

Сложная

Строка codes — категории операций клиента по порядку, по одной букве на операцию. Префикс длины i — повтор, если он равен блоку, записанному подряд k ≥ 2 раз.

Верните по возрастанию i все пары [i, k] для префиксов-повторов, где k — наибольшее возможное число копий (то есть блок кратчайший).

В работе: Т-Банк ищет подписки: история «кафе, такси, кафе, такси, кафе, такси» — цикл из двух операций три раза.

Пример 1

Ввод
codes = "abababa"
Вывод
[[4, 2], [6, 3]]

«abab» = «ab» × 2, «ababab» = «ab» × 3, нечётные длины не делятся на период 2.

Пример 2

Ввод
codes = "aaaa"
Вывод
[[2, 2], [3, 3], [4, 4]]

Блок «a»: длины 2, 3, 4.

Ограничения

  • 0 ≤ длина codes ≤ 10⁵
  • Строчные латинские буквы
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def repeat_prefixes(codes):
СтрокиПрефикс-функцияцельO(n)

Источник: наша задача на данных Т-Банка. Условие пересказано своими словами.