Анализ ДНК марсиан
После недавнего открытия останков древней марсианской цивилизации многие биологи возлагают надежды на анализ ДНК марсиан. Задача усложняется тем, что, в отличие от человеческой ДНК, содержащей всего четыре нуклеотида, у марсиан, вероятно, были более сложные организмы, и их ДНК может содержать до 36 нуклеотидов.
Одним из этапов анализа является обнаружение блоков, отвечающих за определенные свойства организма. Как можно идентифицировать полные блоки? Один из способов — это поиск так называемых максимальных повторений. Рассмотрим ДНК как строку ω, где каждый символ обозначает определенный нуклеотид. Непустая подстрока строки называется максимальным повторением, если она является как лево-ветвящейся, так и право-ветвящейся. Строка α называется лево-ветвящейся, если существуют два разных символа c_1 и c_2, такие что и c_1α, и c_2α являются подстроками $ω (здесь '$' — это символ, который не встречается в ω, введенный для того, чтобы строка, являющаяся префиксом ω и встречающаяся где-то еще в ней, была лево-ветвящейся). Аналогично, α является право-ветвящейся, если и αc_1, и αc_2 являются подстроками ω$ для некоторых различных c_1 и c_2. Длинные максимальные повторения являются хорошими кандидатами на полные блоки.
Дана строка, представляющая ДНК марсианина. Найдите количество различных (как строк) максимальных повторений в ней, длину самого длинного максимального повторения и количество его самых длинных максимальных повторений.
Входные данные
Входной файл содержит непустую строку, состоящую только из заглавных латинских букв и цифр, представляющую ДНК марсианина. Длина строки не превышает 6000.
Выходные данные
Выведите количество максимальных повторений в ДНК, длину самого длинного максимального повторения и количество максимальных повторений этой длины. Если максимальных повторений нет, выведите три нуля.