How to quickly select a substring from a string?

Question

C++ / C#

I have a string, at each iteration, I need to remove the first element and add a new one to the end. Is it possible to do such an update faster than the length of the string? And a more general case: how to select a substring from a string from a certain index to another index (is there such a function in std)?

Answer 1

In the comments , Roman suggested that there is substr from std

Answer 2

Use ring buffer. You will have to pee a little, but what is it for and what will be the complexity of the rest of the work?

Answer 3

You can do this operation not in O(n), but in O(log n), using a Cartesian tree by an implicit key. It must be built on the characters of the given string. Construction is O(n*log(n)), but deleting and inserting from an arbitrary place (including deleting a character from the beginning and inserting it to the end) takes O(log(n).