Рассмотрим строку S = s1s2s3 sn−1sn над алфавитом Σ. Циклическим расширением порядка m строки S назовем строку s1s2s3 sn−1sns1s2 из m символов; это значит, что мы приписываем строку S саму к себе, пока не получим требуемую длину, и берем префикс длины m.

24 октября 2025
Программирование

Условие:

Рассмотрим строку S = s1s2s3 sn−1sn над алфавитом Σ. Циклическим расширением
порядка m строки S назовем строку s1s2s3 sn−1sns1s2 из m символов; это значит, что
мы приписываем строку S саму к себе, пока не получим требуемую длину, и берем префикс
длины m.
Циклической строкой ˜ S назовем бесконечное циклическое расширение строки S.
Рассмотрим суффиксы циклической строки ˜ S. Очевидно, существует не более |S| различ
ных суффиксов: (n + 1)-ый суффикс совпадает с первым, (n + 2)-ой совпадает со вторым,
и так далее. Более того, различных суффиксов может быть даже меньше. Например, если
S =abab, первые четыре суффикса циклической строки ˜ S — это:
˜
S1 = ababababab
˜
S2 = bababababa
˜
S3 = ababababab
˜
S4 = bababababa
Здесь существует всего два различных суффикса, в то время как |S| = 4.
Отсортируем первые |S| суффиксов ˜ S лексикографически. Если два суффикса совпадают,
первым поставим суффикс с меньшим индексом. Теперь нас интересует следующий вопрос:
на каком месте в этом списке стоит сама строка ˜ S?
Например, рассмотрим строку S = cabcab:
(1)
(2)
(3)
(4)
(5)
(6)
˜
S2 = abcabcabca
˜
S5 = abcabcabca
˜
S3 = bcabcabcab
˜
S6 = bcabcabcab
˜
S1 = cabcabcabc
˜
S4 = cabcabcabc
Здесь циклическая строка ˜ S = ˜ S1 находится на пятом месте.
Вам дана строка S. Ваша задача — найти позицию циклической строки ˜ S в описанном
порядке.
Формат входных данных
Во входном файле записана единственная строка S (1 ⩽ |S| ⩽ 1000000), состоящая из
прописных латинских букв.
Формат выходных данных
В выходной файл выведите единственное число — номер строки ˜ S в описанном порядке
среди первых |S| суффиксов.
Примеры
stdin
abracadabra
stdout
3
cabcab
5
Z-функция.Нужно решить на с++

Решение:

Для решения задачи о нахождении позиции циклической строки ˜ S в лексикографическом порядке среди первых |S| суффиксов, мы можем использовать Z-функцию. Давайте разберем решение шаг за шагом. 1. Построение строки для Z-функции: Мы создаем строку, состоящую из S + S, чтобы учесть все возможные циклические сдвиги. Затем мы будем вычислять Z-функцию для этой строки. 2. Вычисление Z-функции: Z-функция для строки S дает нам длины префиксов, совпадающих с подстроками, начинающимися в каждой позиции строки. Мы будем использовать эту функцию, чтобы найти все суффиксы. 3. Сбор уникальных суффиксо...

- Мы считываем строку S. - Создаем строку SS, которая является конкатенацией S с самой собой. - Вычисляем Z-функцию для строки SS. - Собираем все суффиксы, начинающиеся в первых |S| позициях, и сохраняем их в векторе. - Сортируем вектор суффиксов. - Находим позицию ˜ S в отсортированном массиве и выводим её. Этот алгоритм работает за O(n log n) из-за сортировки, что подходит для ограничения задачи.