I. Рудольф и ДНК

Codeforces

IDCF10132I

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Во время экспедиции в кратер Ун'горо Рудольф и его верный спутник Байер собрали множество интересных образцов ископаемой флоры и фауны. Теперь они занимаются исследованием кода ДНК элементального динозавра в попытках определить гены, послужившие причиной элементальной мутации. Код ДНК динозавра представляет собой строку, состоящую из n заглавных букв латинского алфавита. Предполагается, что ген элементальной мутации представляет собой максимальную по длине подстроку кода ДНК, повторяющуюся более одного раза. Помогите Рудольфу написать программу, определяющую ген элементальной мутации. Ввод содержит строку s (1 ≤ |s| ≤ 105), состоящую из заглавных букв латинского алфавита — код ДНК. Если в коде ДНК ген элементальной мутации отсутствует, выведите «_NONE_» (без кавычек). В противном случае в первой строке выведите одно целое число — длину гена элементальной мутации. Во второй строке выведите позиции, начиная с которых в коде ДНК расположен искомый ген. Выведенные позиции должны быть упорядочены по возрастанию, строка индексируется с нуля. Если максимальную подстроку невозможно определить однозначно, во второй строке выведите позиции всех возможных кандидатов. ## Входные Данные Ввод содержит строку s (1 ≤ |s| ≤ 105), состоящую из заглавных букв латинского алфавита — код ДНК. ## Выходные Данные Если в коде ДНК ген элементальной мутации отсутствует, выведите «_NONE_» (без кавычек).В противном случае в первой строке выведите одно целое число — длину гена элементальной мутации. Во второй строке выведите позиции, начиная с которых в коде ДНК расположен искомый ген. Выведенные позиции должны быть упорядочены по возрастанию, строка индексируется с нуля.Если максимальную подстроку невозможно определить однозначно, во второй строке выведите позиции всех возможных кандидатов. ## Примеры Входные данныеEXPEDITIONUNGOROEXPEDITIONВыходные данные100 16Входные данныеABBAВыходные данные10 1 2 3Входные данныеABВыходные данныеNONE [samples]

**Definitions** Let $ s \in \Sigma^* $ be a string of length $ n $, where $ \Sigma = \{A, B, \dots, Z\} $ and $ 1 \leq n \leq 10^5 $. Let $ \mathcal{F}(s) $ be the set of all non-empty substrings of $ s $. For 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 $. Let $ \ell_{\max} = \max \{ |u| \mid u \in \mathcal{F}(s),\ |\text{occ}(u)| \geq 2 \} $. Let $ \mathcal{C} = \{ u \in \mathcal{F}(s) \mid |u| = \ell_{\max},\ |\text{occ}(u)| \geq 2 \} $ be the set of maximal-length repeating substrings. **Constraints** $ 1 \leq |s| \leq 10^5 $, all characters in $ s $ are uppercase Latin letters. **Objective** If $ \mathcal{C} = \emptyset $, output "_NONE_". Otherwise: 1. Output $ \ell_{\max} $. 2. Output the sorted list of all starting positions $ \bigcup_{u \in \mathcal{C}} \text{occ}(u) $, in increasing order.

API Response (JSON)

{
  "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": "Во время экспедиции в кратер Ун'горо Рудольф и его верный спутник Байер собрали множество интересных образцов ископаемой флоры и фауны. Теперь они занимаются исследованием кода ДНК элементального дино...",
      "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...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments