Эхо в ущелье Сары-Челек
В ущелье у озера Сары-Челек живёт эхо: слово, которое читается одинаково слева направо и справа налево (палиндром), оно повторяет особенно громко. Пастух Алмаз прокричал длинную строку 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) хранит все различные палиндромы строки, а их число вхождений можно накопить по суффиксным ссылкам.
Комментарии