c ++有效地获取具有索引的字符串的子字符串

Question

在我的项目中，我必须从 index=0 开始迭代一个大字符串并获得长度为 k 的子字符串。我已经实现了 string::substr() 并且想知道是否还有其他有效的方法。

例如：

std::string S ="ABCDEFGHIJKLMN"

我需要从 S.Just 的开头获取所有长度 =5 的子字符串，例如 "ABCDE"、"BCDEF"、"CDEFG" 等等..

我的实现如下：

    void geekfunc(std::string &str)
{
    unsigned int index=0;
    for (; index<=(str.size()-K);++index)
    {
        ++myseqmap[str.substr(index,K)];
    }
}

该函数已被调用千万次，欢迎尝试其他方法。

Answer 1

如果您使用的是 C++17，则可以使用 string_view 作为您的参数和映射键类型。这样您就不会在每次调用 substr 时都复制字符串内容。只要确保您传递给函数的字符串在您的地图仍在使用时没有被破坏或修改。

std::map<std::string_view, std::size_t> myseqmap;

void geekfunc(std::string_view str)
{
    unsigned int index=0;
    for (; index<=(str.size()-K);++index)
    {
        ++myseqmap[str.substr(index,K)];
    }
}

Answer 2

如果您确实需要创建子字符串的副本（string::substr 需要），我相信您无法通过少于 Omega(m) 调用内存管理器和 Omega(m * k) 来解决这个问题复制总步数，其中 m = n - k + 1。这是因为标准要求每个字符串管理自己的内存。不允许共享（例如使用写时复制习语），因此每个子字符串都将从原始字符串中复制其内容。

如果不需要副本并且您的编译器已经提供 std::string_view you could try using that. Unlike string, a string_view only holds a pointer to a character and a size (which is exactly what you are creating your substrings from anyways). The required pointer can be acquired using string::data。

但是，当使用 string_view 时，您必须确保原始字符串在包含子字符串的容器中一直保留在范围内，并且在创建子字符串后它不会被更改，因为这可能使 string_view 持有的指针无效。这些可以通过将所有内容包装在 class 中来解决，如下所示：

struct substrings{
    const std::string original;
    container<string_view> substrings;
};

其中 container 是您选择的任何容器。

Answer 3

您正在搜索 K-mers 任何给定的字符串。

static vector<string> find_kmers(string Text, int k)
{
    vector<string> kmers;
    int n = Text.length();;

    for (int i = 0; i < n-k+1; i++)
       kmers.push_back(Text.substr(i, k));               
    return kmers;
}

c ++有效地获取具有索引的字符串的子字符串

c++ efficiently get substring of string with index

c++

substr

c++11