在cpp中映射字符串

Question

我想将所有子串存储在unordered_map中。我正在考虑使用stl的substr函数，但最坏的情况是时间复杂度为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);
}