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