D. Все бордеры

Бордер строки - это её собственный префикс, который одновременно является суффиксом. Выведите длины всех бордеров данной строки.

Цепочка ссылок

Наибольший бордер - это в точности $\pi[n-1]$. А следующий по величине - наибольший бордер этого бордера, то есть $\pi[\pi[n-1]-1]$. Продолжая, получаем все бордеры по убыванию:

for (int k = p[n - 1]; k > 0; k = p[k - 1]) answer.push_back(k);

Почему в цепочке оказываются все бордеры: если $b$ - бордер, а $c$ - следующий за ним по величине, то $c$ - бордер строки длины $b$; иначе между ними нашёлся бы бордер побольше.

Сколько их бывает

У строки aaaa...a из $n$ букв бордеров ровно $n-1$ - то есть цепочка бывает длинной, и хранить её надо в массиве, а не считать «сколько-нибудь коротким».

Зато длины бордеров образуют не больше $O(\log n)$ арифметических прогрессий - на этом факте строятся быстрые алгоритмы, где по всем бордерам нельзя пройтись явно.

Связь с периодом

Бордер длины $b$ равносилен периоду длины $n - b$. Наибольшему бордеру соответствует наименьший период - это следующая задача занятия.

Подробнее: «Бордеры и префикс-функция», «Период строки».

Одна строка из строчных латинских букв длиной не больше $10^6$.

В первой строке выведите количество бордеров $k$.

Во второй строке - их длины в порядке убывания. Если бордеров нет, вторую строку оставьте пустой.