1

Тема: Циклические суффиксы

Здравствуйте! Пытаюсь придумать решение задачи E отсюда: https://codeforces.com/gym/100133/attac … oki-ru.pdf (Циклические суффиксы). Понятно, что все строки, начинающиеся на символы, меньшие первого символа исходной строки, будут находиться в отсортированном списке раньше. Подскажите, пожалуйста, как можно решить задачу дальше? Суффиксный массив? Или, может, есть какое-то более элегантное решение с использованием Z-/префикс-функций или хешей? Заранее спасибо!

2

Re: Циклические суффиксы

Если не хочется суффиксным массивом, то альтернативно можно попробовать z-функцией, ведь она позволяет за O(1) сравнивать строку s[0..] со строкой s[i..] (поскольку z-функция сообщает нам позицию первого расхождения в этих двух строках).

3 Отредактировано conway (2021-08-13 00:40:10)

Re: Циклические суффиксы

e-maxx пишет:

Если не хочется суффиксным массивом, то альтернативно можно попробовать z-функцией, ведь она позволяет за O(1) сравнивать строку s[0..] со строкой s[i..] (поскольку z-функция сообщает нам позицию первого расхождения в этих двух строках).

Спасибо за ответ! Таким образом мы можем посмотреть на символ

s[i + z[i]]

и если он меньше

s[z[i]],

то значит, строка, начинающаяся в позиции i идет раньше в списке. Как здесь правильно учесть то, что строки повторяются бесконечное число раз?

То есть, насколько я понимаю, логика примерно следующая.

for (int i = 1; i < m; i++)
  if (s[i + z[i]] < s[z[i]])
    pos++;

4

Re: Циклические суффиксы

Для правильного учёта бесконечности, кажется, ничего особого не нужно, кроме аккуратного разбора случаев? Если мы построим текст как s+s (т.е., припишем строку к себе), то если у строки s[0..] и строки s[i..] совпадающая часть доходит до конца текста, то, кажется, верно будет считать их совпадающими на всей бесконечности. Или есть контрпример?

5

Re: Циклические суффиксы

e-maxx пишет:

Для правильного учёта бесконечности, кажется, ничего особого не нужно, кроме аккуратного разбора случаев? Если мы построим текст как s+s (т.е., припишем строку к себе), то если у строки s[0..] и строки s[i..] совпадающая часть доходит до конца текста, то, кажется, верно будет считать их совпадающими на всей бесконечности. Или есть контрпример?

Действительно, раз есть всего |s| строк, то достаточно построить Z-функцию строки для s + s, а дальше просто смотреть на символы с первого по |s|, при этом проверяя, что i + z(i) не вылезло за всю строку. Большое спасибо!