{"problem":{"name":"I. Рудольф и ДНК","description":{"content":"Во время экспедиции в кратер Ун'горо Рудольф и его верный спутник Байер собрали множество интересных образцов ископаемой флоры и фауны. Теперь они занимаются исследованием кода ДНК элементального дино","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10132I"},"statements":[{"statement_type":"Markdown","content":"Во время экспедиции в кратер Ун'горо Рудольф и его верный спутник Байер собрали множество интересных образцов ископаемой флоры и фауны. Теперь они занимаются исследованием кода ДНК элементального динозавра в попытках определить гены, послужившие причиной элементальной мутации.\n\nКод ДНК динозавра представляет собой строку, состоящую из n заглавных букв латинского алфавита. Предполагается, что ген элементальной мутации представляет собой максимальную по длине подстроку кода ДНК, повторяющуюся более одного раза.\n\nПомогите Рудольфу написать программу, определяющую ген элементальной мутации.\n\nВвод содержит строку s (1 ≤ |s| ≤ 105), состоящую из заглавных букв латинского алфавита — код ДНК.\n\nЕсли в коде ДНК ген элементальной мутации отсутствует, выведите «_NONE_» (без кавычек).\n\nВ противном случае в первой строке выведите одно целое число — длину гена элементальной мутации. \n\nВо второй строке выведите позиции, начиная с которых в коде ДНК расположен искомый ген. Выведенные позиции должны быть упорядочены по возрастанию, строка индексируется с нуля.\n\nЕсли максимальную подстроку невозможно определить однозначно, во второй строке выведите позиции всех возможных кандидатов.\n\n## Входные Данные\n\nВвод содержит строку s (1 ≤ |s| ≤ 105), состоящую из заглавных букв латинского алфавита — код ДНК.\n\n## Выходные Данные\n\nЕсли в коде ДНК ген элементальной мутации отсутствует, выведите «_NONE_» (без кавычек).В противном случае в первой строке выведите одно целое число — длину гена элементальной мутации. Во второй строке выведите позиции, начиная с которых в коде ДНК расположен искомый ген. Выведенные позиции должны быть упорядочены по возрастанию, строка индексируется с нуля.Если максимальную подстроку невозможно определить однозначно, во второй строке выведите позиции всех возможных кандидатов.\n\n## Примеры\n\nВходные данныеEXPEDITIONUNGOROEXPEDITIONВыходные данные100 16Входные данныеABBAВыходные данные10 1 2 3Входные данныеABВыходные данныеNONE\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ s \\in \\Sigma^* $ be a string of length $ n $, where $ \\Sigma = \\{A, B, \\dots, Z\\} $ and $ 1 \\leq n \\leq 10^5 $.  \n\nLet $ \\mathcal{F}(s) $ be the set of all non-empty substrings of $ s $.  \nFor a substring $ u \\in \\mathcal{F}(s) $, let $ \\text{occ}(u) = \\{ i \\in \\{0, \\dots, n - |u|\\} \\mid s[i:i+|u|] = u \\} $ denote the set of starting positions of $ u $ in $ s $.  \n\nLet $ \\ell_{\\max} = \\max \\{ |u| \\mid u \\in \\mathcal{F}(s),\\ |\\text{occ}(u)| \\geq 2 \\} $.  \nLet $ \\mathcal{C} = \\{ u \\in \\mathcal{F}(s) \\mid |u| = \\ell_{\\max},\\ |\\text{occ}(u)| \\geq 2 \\} $ be the set of maximal-length repeating substrings.  \n\n**Constraints**  \n$ 1 \\leq |s| \\leq 10^5 $, all characters in $ s $ are uppercase Latin letters.  \n\n**Objective**  \nIf $ \\mathcal{C} = \\emptyset $, output \"_NONE_\".  \nOtherwise:  \n1. Output $ \\ell_{\\max} $.  \n2. Output the sorted list of all starting positions $ \\bigcup_{u \\in \\mathcal{C}} \\text{occ}(u) $, in increasing order.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10132I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}