Эхо
Текст читают по букве. Для каждой буквы найдите длину самого длинного куска, который кончается на этой букве и уже встречался раньше — кончался на какой-то из предыдущих букв. Куски могут перекрываться: в строке «aaaa» у четвёртой буквы эхо длины 3, потому что «aaa» кончалось на третьей. Если такая буква в тексте ещё не встречалась, эхо — 0.
В третьем тесте — «Евгений Онегин», приведённый к одному виду (строчные буквы, е вместо ё, пробел вместо перевода строки); самое длинное эхо в нём — « и в молчаливом кабинете», 24 знака с пробелом. В четвёртом — геном фага λ, 48 502 нуклеотида.
Вход
Одна строка — текст длиной от 1 до 3 · 10⁵ знаков в кодировке UTF-8, без пробелов в начале и в конце. Длина считается в знаках, а не в байтах.
Выход
В одной строке через пробел — эхо каждой буквы по порядку.
Примеры
Пример 1
abcbc
0 0 0 1 2
Пример 2
колокол
0 0 0 1 1 2 3
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Если у буквы i эхо длины L, каким может быть эхо буквы i + 1? Больше L + 1 — нет: кусок, который кончается на i + 1 и встречался раньше, без последней буквы тоже встречался раньше.
2Подсказка 2
Самый длинный суффикс прочитанного, который кончался и раньше, — это ровно то, на что указывает суффиксная ссылка в автомате. Автомат строится по букве — значит, ответ можно снимать после каждого шага.
3Идея
Строим суффиксный автомат онлайн. После буквы i состояние last — это класс строки из первых i букв, его концы — одна позиция i. Суффиксная ссылка ведёт в класс самого длинного суффикса, у которого концов больше, то есть который кончался и раньше. Его длина len(link(last)) — ответ.
4Разбор
Это обычное построение из статьи, только после каждой буквы выписываем len ссылки нового состояния. Копия ничего не меняет в ответе для уже прочитанных букв, а новой ссылке как раз нужна: если суффикс встречался раньше, но его класс шире, ссылка указывает на копию нужной длины.
4+Решение
5Сложность
O(n) на весь текст: построение линейно, ответ на каждом шаге — одно чтение длины.
6Типичные ошибки
- Искать раньше find-ом. Это
wrong.py: эхо растёт не больше чем на единицу, поэтому пробуем длины от прошлого ответа плюс один вниз и ищем кусок в прочитанном. Ответы верные, но неудачный поиск читает всё прочитанное. Уже на «Онегине» в третьем тесте эхо в среднем пять знаков, почти каждая буква кончается неудачей — и это 139 тысяч проходов по тексту. - Без копий. Если ссылкой нового состояния сделать q, даже когда len(q) больше len(p) + 1, длина по ссылке окажется больше настоящего эха. Это видно уже в первом примере, на четвёртой букве, а в девятом тесте из случайных a и b копия появляется почти на каждом шаге. Зато в слове Фибоначчи из восьмого теста копий нет ни одной.
- Эхо без перекрытия. В строке из одних «a» в седьмом тесте ответ у i-й буквы — i − 1: прошлое вхождение может налезать на нынешнее.
- Вывод. Ответов 3 · 10⁵ — печатать их по одному медленно; соберите строку целиком.