在C/C++中查找包含子字符串的字符串，该子字符串的字符可以以任意顺序出现。

Question

假设我有一个字符串"abcdpqrs"， 现在，由于这些字符是在一起的，"dcb"可以被计算为上述字符串的子字符串。 同样地，“pdq”是该字符串的一部分。但是“bcpq”不是。我希望你能理解我的需求。 有没有更有效的方法来做到这一点呢？ 我所想到的只有借助哈希来实现这一点。但是即使在O(n)程序中需要在许多情况下进行回溯，它也要花费很长时间。任何帮助将不胜感激。

- MrTambourineMan

---

... 正则表达式？ - aruisdante

你是指使用C语言的“regex”库吗？我还没有尝试过。能否提供一些如何使用它的帮助？ - MrTambourineMan

正则表达式是一个长而复杂的主题，整本书都可以写关于它。但是这里有一个很好的与语言无关的教程集，介绍了一般概念。你使用C++ 11吗？如果不是，要在C++中使用正则表达式，你需要使用第三方库，比如boost::regex。 - aruisdante

同样，无论是在 needle 还是 haystack 中，相同的字符是否可以出现多次？ - Ben Voigt

一根针找一堆干草。但字符可以在两者之间是多个的。 - MrTambourineMan

Answer 1

这里有一个O(n * 字母表大小)的解法：

我们需要维护一个数组count[a]，表示字符a在当前窗口[pos; pos + 子串长度 - 1]中出现的次数。当窗口向右移动1位时，可以在O(1)时间内重新计算(count[s[pos]]--, count[s[pos + substring lenght]]++, pos++)。现在我们只需要检查每个位置，count数组是否与子字符串的count数组相同(它只需要计算一次)。

实际上，它可以改进为O(n + 字母表大小)：

不使用朴素方法比较count数组，而是维护差异数量diff = 当前窗口中与子串的count值不同的字符数。关键观察点是，当我们应用count[c]--或count[c]++时，diff会以明显的方式变化(它只取决于count[c]值，要么被增加、减少或保持不变)。两个count数组仅在当前位置的diff为零时才相同。

- kraskevich

---

是的...我有一个更好的解决方案，适用于不允许重复的情况，但我认为当允许重复时，这是最优的。 - Ben Voigt

我认为26*n是这个问题的唯一最优解？ - MrTambourineMan

是的，我的意思是，假设我们只考虑小写字母（a-z）。 - MrTambourineMan

我想出了O(n + 字母表大小)的解决方案，并且我已经编辑了我的答案。 - kraskevich

事实上，我一开始误解了一些东西。我认为这是一个好方法。然而，如果n非常大，而m（搜索字符串）很小，我的建议在某些情况下可能具有优势。但我同意这通常是最好的答案。 - benjist

Answer 2

你可以使用正则表达式（如boost或Qt）来实现。或者你也可以使用这种简单的方法。你知道要在字符串str中搜索长度为k的字符串s。因此，从str中取出每个连续的k个字符，并检查这些字符中是否有任何一个出现在s中。

起点（一个朴素的实现方案，可进行进一步优化）：

#include <iostream>

/* pos position where to extract probable string from str
*  s string set with possible repetitions being searched in str
*  str original string
*/
bool find_in_string( int pos, std::string s, std::string str)
{
    std::string str_s = str.substr( pos, s.length());
    int s_pos = 0;

    while( !s.empty())
    {
        std::size_t found = str_s.find( s[0]);
        if ( found!=std::string::npos)
        {
            s.erase( 0, 1);
            str_s.erase( found, 1);
        } else return 0;
    }

    return 1;
}

bool find_in_string( std::string s, std::string str)
{
    bool found = false;
    int pos = 0;    
    while( !found && pos < str.length() - s.length() + 1)
    {
        found = find_in_string( pos++, s, str);
    }

    return found;
}

使用方法：

int main() {

    std::string s1 = "abcdpqrs";
    std::string s2 = "adcbpqrs";
    std::string searched = "dcb";
    std::string searched2 = "pdq";
    std::string searched3 = "bcpq";
    std::cout << find_in_string( searched, s1);
    std::cout << find_in_string( searched, s2);
    std::cout << find_in_string( searched2, s1);
    std::cout << find_in_string( searched3, s1);

    return 0;
}

打印：1110

http://ideone.com/WrSMeV

- 4pie0

---

你的想法有一个警告（也许？）...由于集合只获取每个元素一次，如果他尝试在“abc”中搜索“aaa”，会发生什么？ - nightshade

这是一个域范围错误，但我们可以轻松处理。 - 4pie0

我并不是在批评，我真的很喜欢你的想法，非常聪明……但如果允许重复，则需要进行适应。 - nightshade

Answer 3

假设你有一个字符串 "axcdlef"，想要搜索 "opde"：

bool compare (string s1, string s2)
{
  // sort both here
  // return if they are equal when sorted;
}

对于这个例子，您需要使用大小为4的以下子字符串调用此函数（与“opde”长度相同）：

“axcd” “xcdl” “cdle” “dlef”

  bool exist = false;

  for (/*every split that has the same size as the search */)
      exist = exist || compare(currentsplit, search);

- nightshade

---

在“adedem”中检查“dde”怎么样？ - MrTambourineMan

@rocker：这是匹配成功的代码：a(ded)em。 - Ben Voigt

当您进行第二次搜索（长度为3的第二个字符串）时，您将向函数发送“ded”和“dde”，它们将被排序并返回true。 - nightshade

哦，好的，我以为你是通过子字符串大小来滑动窗口。是的，那样可以行得通。但是由于需要排序，所以不会被优化。 - MrTambourineMan

好的，另一个你需要对数组进行其他操作...我正在用 map 写一个解决方案，然后看到这个使用排序的方法，就停下来了，我会写我想到的 map 方法。 - nightshade

Answer 4

要使用数组来实现这个功能，您需要一些额外的代码来映射每个字符在其中的位置...除非您知道您只使用'a' - 'z'或类似的内容，那么您可以从'a'中减去相应的值来获取位置。

bool compare(string s1, string s2)
{
   int v1[SIZE_OF_ALFABECT];
   int v2[SIZE_OF_ALFABECT];
   int count = 0;
   map<char, int> mymap;

  // here is just pseudocode
   foreach letter in s1:
      if map doesnt contain this letter already:
           mymap[letter] = count++;

 // repeat the same foreach in s2

 /* You can break and return false here if you try to add new char into map, 
  that means that the second string has a different character already... */

 // count will now have the number of distinct chars that you have in both strs

 // you will need to check only 'count' positions in the vectors

 for(int i = 0; i < count; i++)
    v1[i] = v2[i] = 0;

 //another pseudocode
   foreach letter in s1:
      v1[mymap[leter]]++;
   foreach letter in s1:
      v2[mymap[leter]]++;

  for(int i = 0; i < count; i++)
      if(v1[i] != v2[i])
          return false;

  return true;
}

- nightshade

Answer 5

这里有一个O(m)的最佳情况，O(m!)的最坏情况解决方案 - 其中m是您搜索字符串的长度：

使用后缀树，例如Ukkonnen Trie（有一些漂浮在周围，但我目前没有链接），并搜索子字符串的任何排列。请注意，任何查找仅需要每个要搜索的字符串字符的O(1)，而不管n的大小。

然而，虽然n的大小无关紧要，但对于大m来说，这变得不切实际。

如果n足够小且愿意为索引大小牺牲查找性能，则后缀树可以存储包含原始字符串所有排列的字符串。

然后查找将始终为O(m)。

我建议在一般情况下选择接受的答案。但是，在这里，您有一个可以在小子字符串和大字符串上执行（更）好的建议。

- benjist

---

以下是针对以下示例的工作原理：s =“abc”要搜索的子字符串=“cab”？ - kraskevich

这个例子不起作用。但是你的例子是错误的。原帖明确指出这些字符是“在一起”的。 - benjist

不，他说字符的顺序并不重要（也就是说，如果任何一个子串的排列组合在传统意义上是一个子串，那么它就匹配）。 - kraskevich

然后使用该字符串的排列进行搜索。在给定字符之后检查字符的存在始终是O(1)。因此，在最坏情况下，搜索性能将为O(m!) - 如果需要在找到相应的匹配之前检查所有排列。在最佳情况下，当子字符串有精确匹配时，为O(m)。或者，如果字符串不太大，则构建所有可能的字符串排列的后缀字典树。然后您将坚持O(m)。 - benjist