#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);
}