Как быстро выбирать подстроку у строки?

Question

[a2NaF]

У меня есть строка, на каждой итерации нужно убирать первый элемент и добавлять в конец новый. Можно ли делать такое обновление быстрее, чем за длину строки? И более обобщенный случай: как выбрать у строки подстроку с определенного индекса до другого индекса (есть ли такая функция в std)?

Comments

[Roman]

как выбрать у строки подстроку с определенного индекса до другого индекса

чем банальная https://en.cppreference.com/w/cpp/string/basic_str...
не угодила?

Можно ли делать такое обновление быстрее, чем за длину строки?

Под это больше подходит очередь https://en.cppreference.com/w/cpp/container/deque

[a2NaF]

Roman, не знал про substr, т.к. лишь поверхностно изучаю, а очередь не всегда может подойти по решению. Спасибо!

Answer 1

[a2NaF]

В комментариях Roman подсказал, что из std есть substr

Comments

[Mercury13]

Но substr — это O(N).

Answer 2

[Mercury13]

Использовать кольцевой буфер. Придётся пописать немного, но на что это нужно и какова будет сложность остальных работ?

Comments

[a2NaF]

Мне для обычной string из std нужно было

[Mercury13]

a2NaF, Для std::string невозможно быстрее.

Answer 3

[the1vanyes]

Можно сделать данную операцию не за O(n), а за O(log n), используя декартово дерево по неявному ключу. Строить его нужно на символах данной строки. Построение - О(n*log(n)), зато удаление и вставка из произвольного места(в т.ч. удаление символа из начала и вставка в конец) за O(log(n).

Comments

[Roman]

вопрос вроде про "чистую" строку был. как непосредственно к строке это можно применить не копируя в/из нее элементы в другую структуру данных. если на то уж пошло в std::deque вставка и удаление в начале и в конце O(1).