Блог

Главная - Вопросы по программированию - Строка карты в cpp

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

#c #string #maps

Вопрос:

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

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

Комментарии:

1. попробуйте представление строк. Вы можете очень эффективно представлять подстроку. Однако сохранение всех подстрок на карте будет медленным, что бы вы ни пытались. Использование карты в качестве кэша для уже компьютерного результата с заданной подстрокой будет намного лучше

2. Любопытно, как вы планируете использовать эту карту, я подозреваю, что именно на этом мы должны сосредоточиться

Ответ №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);
}
Метки: