Назовём строкой последовательность из маленьких букв латинского алфавита. Строкой, например, является пустая последовательность, слово «aabaf» или бесконечная последовательность букв «a».

i-ый суффикс S_i строки S — это строка S, из которой вырезаны первые i букв; так, для строки S = aabaf суффиксы будут такими:

1. S₀ = aabaf
2. S₁ = abaf
3. S₂ = baf
4. S₃ = af
5. S₄ = f
6. S₅ = S₆ = S₇ = ... = «»

Суффиксы определены для всех i \(\ge\) 0.

Циклическое расширение S *  конечной строки S — это строка, полученная приписыванием её к самой себе бесконечное количество раз. Так,

1. S *  = S * ₀ = aabafaabafaabafaa...
2. S * ₁ = abafabafabafabaf...
3. S * ₂ = bafbafbafbafbafb...
4. S * ₃ = afafafafafafafaf...
5. S * ₄ = ffffffffffffffff...
6. S * ₅ = S * ₆ = S * ₇ = ... = ""

По заданной строке S выясните, сколько её суффиксов S_i имеют такоей же циклическое расширениe, как и строка S, то есть количество таких i, что S *  = S * _i.

Дана строка S. Назовем ее подстрокой строку с i-го по j-й символ (i ≤ j). Ваша задача — посчитать количество различных подстрок данной строки.

Привидение Петя любит играть со своими кубиками. Он любит выкладывать их в ряд и разглядывать свое творение. Однако недавно друзья решили подшутить над Петей и поставили в его игровой комнате зеркало. Ведь всем известно, что привидения не отражаются в зеркале! А кубики отражаются. Теперь Петя видит перед собой N цветных кубиков, но не знает, какие из этих кубиков настоящие, а какие — всего лишь отражение в зеркале. Помогите Пете! Выясните, сколько кубиков может быть у Пети. Петя видит отражение всех кубиков в зеркале и часть кубиков, которая находится перед ним. Часть кубиков может быть позади Пети, их он не видит.

Известно, что в солнечной системе есть 8 планет и один планетоид. Мало кто знает, что ещё есть секретная планета, населенная медведями. Именно туда ассоциация Savez отправляет бравого генерала Хенрика для изучения медведей. Выяснилось, что медведи умеют телепортироваться. Расчётливый генерал Хедрик решил завербовать их в свою армию.

У одного медведя есть N строк (обозначим i -ю из них x _i ). Исследования показывают, что количество раз, которое может телепортироваться медведь равно длине наибольшей подпоследовательности этих строк, удовлетворяющей такому правилу: строки x _i и x _j ( i < j ) могут принадлежать одной такой последовательности, если x _i является и префиксом, и суффиксом x _j .

Помогите уставшему от долгого полёта генералу Хендрику определить, сколько телепортаций сможет сделать данный медведь.

Недавно произошла утечка информации из мега-популярной социальной сети. Среди конфиденциальной информации, попавшей в сеть, оказались и пароли всех пользователей.

Михаил, школьник, увлекающийся компьютерной безопасностью, нашёл произошедший инцидент очень интересным. Экспериментируя с социальной сетью, он нашёл ещё одну брешь в её системе безопасности! Войти в аккаунт можно, если ввести строку, содержащую настоящий пароль от аккаунта как подстроку. Например, если пользователь, чей пароль « abc » введёт « abc », « abcd » или « imaabcnema », у него успешно получиться авторизоваться в системе, но у него не получится если он введёт « axbc ».

Миша хочет узнать, сколько существует упорядоченных пар пользователей таких, что если первый пользователь введёт пароль, то он сможет войти в аккаунт второго пользователя.