Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
Активные темы Темы без ответов
Настройки поиска
e-maxx пишет:Для правильного учёта бесконечности, кажется, ничего особого не нужно, кроме аккуратного разбора случаев? Если мы построим текст как s+s (т.е., припишем строку к себе), то если у строки s[0..] и строки s[i..] совпадающая часть доходит до конца текста, то, кажется, верно будет считать их совпадающими на всей бесконечности. Или есть контрпример?
Действительно, раз есть всего |s| строк, то достаточно построить Z-функцию строки для s + s, а дальше просто смотреть на символы с первого по |s|, при этом проверяя, что i + z(i) не вылезло за всю строку. Большое спасибо!
e-maxx пишет:Если не хочется суффиксным массивом, то альтернативно можно попробовать z-функцией, ведь она позволяет за O(1) сравнивать строку s[0..] со строкой s[i..] (поскольку z-функция сообщает нам позицию первого расхождения в этих двух строках).
Спасибо за ответ! Таким образом мы можем посмотреть на символ
и если он меньше
то значит, строка, начинающаяся в позиции i идет раньше в списке. Как здесь правильно учесть то, что строки повторяются бесконечное число раз?
То есть, насколько я понимаю, логика примерно следующая.
for (int i = 1; i < m; i++)
if (s[i + z[i]] < s[z[i]])
pos++;
Здравствуйте! Пытаюсь придумать решение задачи E отсюда: https://codeforces.com/gym/100133/attac … oki-ru.pdf (Циклические суффиксы). Понятно, что все строки, начинающиеся на символы, меньшие первого символа исходной строки, будут находиться в отсортированном списке раньше. Подскажите, пожалуйста, как можно решить задачу дальше? Суффиксный массив? Или, может, есть какое-то более элегантное решение с использованием Z-/префикс-функций или хешей? Заранее спасибо!
Сообщений найдено [ 3 ]