Эхо в ущелье Сары-Челек


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 3.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

В ущелье у озера Сары-Челек живёт эхо: слово, которое читается одинаково слева направо и справа налево (палиндром), оно повторяет особенно громко. Пастух Алмаз прокричал длинную строку s из строчных латинских букв.

Громкость палиндрома P равна |P| · occ(P), где |P| — длина палиндрома, а occ(P) — сколько раз он встречается в s как подстрока (вхождения могут перекрываться).

Рисунок

Найдите количество различных палиндромов среди подстрок s и наибольшую громкость палиндрома.

Входные данные

В единственной строке — строка s (1 ≤ |s| ≤ 10⁶) из строчных латинских букв.

Выходные данные

Выведите два числа: количество различных непустых палиндромов-подстрок и наибольшую громкость.

Пример 1

Вход:

abacaba

Выход:

7 7

Пояснение

Палиндромы строки abacaba: a, b, c, aba, aca, bacab, abacaba — всего 7. a встречается 4 раза (громкость 4), aba — 2 раза (громкость 6), abacaba — 1 раз (громкость 7). Наибольшая громкость 7.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов |s| ≤ 200.

Подсказка

Дерево палиндромов (eertree) хранит все различные палиндромы строки, а их число вхождений можно накопить по суффиксным ссылкам.


Комментарии

Еще нет ни одного комментария.