Задача 4 из 14

Цепочка групп KLMN

Время 2 с · память 256 МБ

Строка состоит из символов K, L, M и N. Определите максимальное количество идущих подряд символов, которые образуют последовательность из групп KLMN, следующих одна за другой в указанном порядке. В начале и в конце искомой последовательности группа KLMN может быть неполной.

Искомая последовательность является непрерывным фрагментом бесконечного повторения KLMNKLMNKLMN... и должна содержать не менее одной полной группы KLMN. Неполная группа в начале может быть только LMN, MN или N, а в конце — только K, KL или KLM. Например, подходят последовательности MNKLMNKLMNK и NKLMNKLMNKL.

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

Во входных данных содержится одна непустая строка длиной не более 10610^6 символов. Гарантируется, что искомая последовательность существует.

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

Выведите одно число — количество символов в найденной последовательности.

Примеры

Ввод 1
MNKLMNKLMNK
Вывод 1
11
Ввод 2
LMNKKLMNKL
Вывод 2
6

Примечание

В первом примере подходит вся строка. Во втором примере символы LMNK в начале строки стоят в нужном порядке, но полной группы KLMN не содержат; искомая последовательность — KLMNKL.

Решение
Загрузка редактора…
Результат появится здесь

Черновик сохраняется в этом браузере.

Ошибка в задаче