Анализируя битовые (еще и специальные) строки
Вы думаете, что анализировать строки просто? Это так, но только если Вы не во сне. Но Вы во сне. Неожиданно, правда? Но... я боюсь, что это не сон, в котором Вы хотели бы оказаться. В Вашем сне имеется строка бит, длинная строка бит, с которой Вам придется иметь дело. И Вы четко понимаете, что нужно сделать, чтобы покинуть этот ужасный сон прямо сейчас: необходимо найти лучшую специальную строку.
К счастью, Вы вчера прочитали книгу по теории специальных строк. Вам удалось только вспомнить странное определение специальных строк, которое выглядело следующим образом.
Пусть у Вас имеется строка бит 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_1∙P_1 > L_2∙P_2.
Итак, Ваша задача проста... или нет? Найдите наилучшую специальную строку - такую специальную строку, что никакая из остальных специальных строк не лучше ее.
Входные данные
Одна строка S (2 ≤ |S| ≤ 2*10^5), состоящая из нулей и единиц.
Выходные данные
Первая строка должна содержать значение L∙P, где L - длина наилучшей специальной строки, а P - число ее вхождений в S в качестве подстроки. Вторая строка должна содержать саму наилучшую строку. Если таковых имеется несколько, то вывести любую.
Гарантируется, что как минимум одна специальная строка является подстрокой S.