Строка карты в cpp

Question

Я хочу сохранить все подстроки в unordered_map. Я думаю использовать substr функцию stl, но в худшем случае сложность времени оказывается равной O (n), и когда я собираюсь использовать внутри цикла для всехиндексы строки это даст мне O (n ^ 2).

Можем ли мы сделать что-то лучше в O (n), используя указатель или что-то еще, чтобы я мог получить доступ к подстроке позже.

Answer 1

Если вы не хотите копировать подстроки в карту, вы можете использовать std::string_view для сохранения вида подстроки.Это стоит вам указатель и длина, поэтому он настолько эффективен, насколько это возможно.

Вы можете построить вектор из всех подстрок, как

int main()
{
    std::string word = "word";
    auto size = word.size();
    std::vector<std::string_view> parts;
    parts.reserve(size * (size + 1)/2); // reserve space for all the sub strings
    for(size_t i = 0; i < size; ++i)
        for(size_t j = i; j < size; ++j)
            parts.emplace_back(word.data() + i, j - i + 1);
}