eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Анализируя битовые (еще и специальные) строки

Анализируя битовые (еще и специальные) строки

Лимит времени 3 секунды
Лимит использования памяти 256 MiB

Вы думаете, что анализировать строки просто? Это так, но только если Вы не во сне. Но Вы во сне. Неожиданно, правда? Но... я боюсь, что это не сон, в котором Вы хотели бы оказаться. В Вашем сне имеется строка бит, длинная строка бит, с которой Вам придется иметь дело. И Вы четко понимаете, что нужно сделать, чтобы покинуть этот ужасный сон прямо сейчас: необходимо найти лучшую специальную строку.

К счастью, Вы вчера прочитали книгу по теории специальных строк. Вам удалось только вспомнить странное определение специальных строк, которое выглядело следующим образом.

Пусть у Вас имеется строка бит T длины n. Биты T обозначим через T_1, T_2, ..., T_n. Обозначим через A(i, j) и B(i, j) количество 0-бит и 1-бит среди T_i, T_{i+1}, ..., T_{j }соответственно. Строка T называется специальной, если для каждого i между 1 и n включительно имеют место следующие соотношения: A(1, i) ≥ B(1, i) и A(i, n) ≤ B(i, n).

Однако Вас не удовлетворяет любая из специальных строк. Вам нужна наилучшая специальная строка. Сон был слишком странным, поэтому и правило определяющее какая из строк лучше, также выглядит очень странным. Пусть L_1 и L_2 - длины двух строк, а P_1 и P_2 - количество раз, которое они встречаются во входной строке S в качестве подстрок соответственно. Первая строка считается лучше второй, если L_1P_1 > L_2∙P_2.

Итак, Ваша задача проста... или нет? Найдите наилучшую специальную строку - такую специальную строку, что никакая из остальных специальных строк не лучше ее.

Входные данные

Одна строка S (2 ≤ |S| ≤ 2*10^5), состоящая из нулей и единиц.

Выходные данные

Первая строка должна содержать значение L∙P, где L - длина наилучшей специальной строки, а P - число ее вхождений в S в качестве подстроки. Вторая строка должна содержать саму наилучшую строку. Если таковых имеется несколько, то вывести любую.

Гарантируется, что как минимум одна специальная строка является подстрокой S.

Пример

Входные данные #1
00111001110101
Выходные данные #1
8
0011
Автор Геннадий Короткевич
Источник Gennady Korotkevich Contest 1, Petrozavodsk Training Camp, Day 1, Friday, August 23, 2013