c++ - 在字符串中查找随机排序的子字符串

Question

对于问题的第一部分，我们给出了一长串输入，我们必须计算它的出现次数。例如。

Input = AXBHAAGHXAXBH
Find = AXBH
Output = 2

这可以通过使用 string.find("term") 循环来实现。例如。

#include <string>
#include <iostream>
int main()
{
   int occurrences = 0;
   std::string::size_type pos = 0;
   std::string inputz = "AXBHAAGHXAXBH";
   std::string target = "AXBH";
   while ((pos = inputz.find(target, pos )) != std::string::npos) {
          ++ occurrences;
          pos += target.length();
   }
   std::cout << occurrences << std::endl;

}

但是，我不确定第二部分该怎么做，它需要考虑到随机结构:随机结构是指我们发现的任何方向。重要说明:查找结果始终分组在一起，但可以具有不同的结构。我不想用例，因为一些样本发现太大，例如。查找 AXBHNMB 需要考虑的情况太多，并且更喜欢更通用的方法。

Eg. AXBH is find, then AXHB is also acceptable for the occurence

一个恰当的例子:

Input = AXBHAAGHXAXBH**ABHX**NBMN**AHBX**
Find = AXBH
Output = 4

如果您为给定的示例编写代码，并附上指向您使用的任何新功能的解释/解释的链接，则更可取。

Answer 1

您是正确的，检查所有排列将花费大量时间。幸运的是我们不需要那样做。我们可以做的是将要查找的字符串存储在 std::map<char, int> 中。/std::unordered_map<char, int>然后从字符串中抓取子字符串进行搜索，将它们转换为相同类型的映射并查看这些映射是否相等。这让我们可以在不关心顺序的情况下使用比较，它只是确保我们拥有正确数量的每个字符。所以我们会有类似的东西

int main()
{
    std::string source = "AHAZHBCHZCAHAHZEHHAAZHBZBZHHAAZAAHHZBAAAAHHHHZZBEWWAAHHZ ";
    std::string string_to_find = "AAHHZ";
    int counter = 0;

    // build map of the characters to find
    std::unordered_map<char, int> to_find;
    for (auto e : string_to_find)
        ++to_find[e];

    // loop through the string, grabbing string_to_find chunks and comparing
    for (std::size_t i = 0; i < source.size() - string_to_find.size();)
    {
        std::unordered_map<char, int> part;
        for (std::size_t j = i; j < string_to_find.size() + i; ++j)
            ++part[source[j]];

        if (to_find == part)
        {
            ++counter;
            i += string_to_find.size();
        }
        else
        {
            ++i;
        }
    }

    std::cout << counter;
}