Фраза k раз
В третьем томе Толстой приводит диспозицию Наполеона к сражению, а потом разбирает её по пунктам: это не могло быть сделано, а то не было и не могло быть исполнено. Какие фразы автор повторяет чаще других — вопрос для исследователя стиля, и программа должна отвечать на него быстро для любого k.
Дан текст и число k. Найдите самый длинный кусок текста, который встречается в нём не меньше k раз. Вхождения могут перекрываться: в «aaaa» кусок «aa» встречается три раза. Пробелы и знаки препинания — обычные знаки. Если самых длинных кусков несколько, нужен наименьший в словарном порядке (знаки сравниваются по номерам в Юникоде).
Вход
В первой строке число k. Во второй — текст в UTF-8 без переводов строки, от k до 100 000 знаков; 2 ≤ k. Длина считается в знаках, а не в байтах.
Выход
В первой строке — длина найденного куска, во второй — сам кусок. Если ни один знак не встречается k раз, выведите 0 и пустую строку.
Примеры
Пример 1
2 abracadabra
4 abra
Пример 2
3 abracadabra
1 a
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 11 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Кусок встречается k раз — значит, k суффиксов текста начинаются с него. Где эти суффиксы стоят в суффиксном массиве?
2Подсказка 2
Суффиксы с общим началом стоят в массиве подряд. Для k суффиксов подряд, с номерами от j − k + 1 до j, какое у них самое длинное общее начало?
3Подсказка 3
Общее начало нескольких суффиксов подряд — минимум lcp между соседями внутри этой группы: k − 1 чисел. Нужен максимум таких минимумов по всем окнам.
4Идея
Ответ — максимум по окнам из k − 1 соседних значений lcp от минимума в окне. Минимум скользящего окна считают очередью с возрастающими значениями: новое значение выталкивает с конца все, что не меньше его, а начало очереди уходит, когда выпадает из окна. Как в статье о скользящем окне.
5Разбор
Суффиксный массив и lcp — как в статье. Потом один проход по lcp с очередью: на каждом шаге в начале очереди — минимум последних k − 1 значений. Лучший минимум и суффикс, на котором он достигнут, дают ответ. Окна идут в порядке массива, поэтому первое окно с наибольшим минимумом даёт словарно наименьший кусок.
В третьем тесте, главе с диспозицией, при k = 2 ответ — 78 знаков: «и перейдет по своим трем мостам, следуя на одной высоте с дивизиями Морана и» — сначала в тексте диспозиции, потом в разборе. При k = 3 — «не было и не могло быть»: это и есть рефрен главы. В первой части романа пять раз встречается «, — сказала Анна Павловна, ».
5+Решение
6Сложность
Массив — O(n log n), lcp — O(n), проход с очередью — O(n): каждый индекс входит в очередь и выходит из неё один раз. Двоичный поиск по длине с хешами — тоже рабочий путь, O(n log n), но в нём надо считать вхождения каждого хеша и помнить о коллизиях.
7Типичные ошибки
- Только соседи. Наибольшее lcp двух соседей — ответ для k = 2. Для k = 3 в «abracadabra» оно даёт «abra», а «abra» встречается только дважды; верный ответ — «a».
- Окно из k значений lcp. На k суффиксов приходится k − 1 промежутков между ними, а не k.
- Без перекрытий. В теломере кусок длиной 94 006 знаков встречается тысячу раз, сдвигаясь на одно звено: вхождения перекрываются, и это разрешено.