C++高效获取字符串的子串

Question

在我的项目中，我需要从索引0开始迭代一个大字符串，并获取长度为k的子字符串。我已经实现了string::substr()，但想知道是否有其他高效的方法。

例如：

std::string S ="ABCDEFGHIJKLMN"

我需要获得从字符串S的开头开始长度为5的所有子串。就像"ABCDE"，"BCDEF"，"CDEFG"等一样。

我的实现如下：

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

这个函数被调用了一千万次，欢迎尝试其他方法。

- Krcn U

---

我不明白你想要实现什么：你是想得到输入字符串中所有长度为 k 的子串吗？ - Rerito

你想通过这个函数解决的实际问题是什么？请花些时间阅读关于XY问题的内容，并思考它如何与你的问题相关。 - Some programmer dude

我已经编辑了问题以获得更清晰的表述。 - Krcn U

Answer 1

如果您使用的是C++17，您可以将string_view用作参数和映射键类型。这样，每次调用substr时，您就不会复制字符串内容。只需确保在使用map时不要销毁或修改传递给函数的字符串即可。

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

- Joseph Thomson

Answer 2

如果你确实需要创建子字符串的副本（即string::substr所做的），我认为你至少需要进行 Omega(m)次对内存管理器的调用和 Omega(m * k)次复制步骤，其中m = n - k + 1。这是因为标准要求每个字符串都要管理自己的内存。共享（例如使用写时复制惯用语）是不允许的，因此每个子字符串将从原始字符串复制其内容。

如果不需要副本并且编译器已经提供了std::string_view，则可以尝试使用它。与string不同，string_view仅包含指向字符的指针和大小（这正是您从中创建子字符串的内容）。所需的指针可以使用string::data获取。

然而，当使用string_view时，您必须确保原始字符串在包含子字符串的容器持续存在，并且在创建子字符串后不会被更改，因为这可能会使string_view所持有的指针无效。可以通过像这样将所有内容封装在一个类中来解决这些问题：

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

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

- Pandatyr

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

- Sahib Yar