如何在字符串中找到所有子字符串的位置？

Question

我想在一个大字符串中搜索一个字符串的所有位置。

- Herr Char

Answer 1

另外两个答案是正确的，但它们非常缓慢且复杂度为O(N^2)。但是有一种叫做Knuth-Morris-Pratt算法，它可以在O(N)复杂度下找到所有子字符串。

编辑：

还有另一种算法：所谓的“Z函数”，复杂度为O(N)，但我找不到英文来源（可能是因为还有另一个同名的更著名的算法 - 瑞曼的Z函数），所以我将在此处放置其代码并解释其作用。

void calc_z (string &s, vector<int> & z)
{
    int len = s.size();
    z.resize (len);

    int l = 0, r = 0;
    for (int i=1; i<len; ++i)
        if (z[i-l]+i <= r)
            z[i] = z[i-l];
        else
        {
            l = i;
            if (i > r) r = i;
            for (z[i] = r-i; r<len; ++r, ++z[i])
                if (s[r] != s[z[i]])
                    break;
            --r;
        }
}

int main()
{
    string main_string = "some string where we want to find substring or sub of string or just sub";
    string substring = "sub";
    string working_string = substring + main_string;
    vector<int> z;
    calc_z(working_string, z);

    //after this z[i] is maximal length of prefix of working_string
    //which is equal to string which starting from i-th position of
    //working_string. So the positions where z[i] >= substring.size()
    //are positions of substrings.

    for(int i = substring.size(); i < working_string.size(); ++i)
        if(z[i] >=substring.size())
            cout << i - substring.size() << endl; //to get position in main_string
}

- Mihran Hovsepyan

---

嗯，你不觉得std::string::find的作者可能已经在底层实现了KMP算法吗？事实上，随着新的SSE4.2指令的出现，这种类型的优化可能已经在低级函数（如glibc中的strstr）中可用 - 除非你在自己的代码中使用这些指令，否则你很难超越这些低级函数的性能。最终结果是，除非你可以经验证明它真的很慢，否则不要重新发明轮子... 只是我的看法。 - Nim

你可以进行自我测试。考虑主字符串为 "a"（重复了一百万次）+"b"+"a"（重复了一百万次），子字符串为 "a"（重复了九十九万九千九百九十九次）。使用 std::string::find 和 @Kiril Kirov 的代码，你的程序会需要 2-3 天才能运行完，但我的程序会立即返回结果。 - Mihran Hovsepyan

您可能还想考虑使用Boyer-Moore算法，它的时间复杂度为O(N)，并且在需要查找较长子串时性能更好。 - Hasturkun

当描述字符串查找算法的运行时间复杂度为O(N)或O(N*N)时，有点不合适，因为实际上有两个参数决定了运行时间，即N_haystack和N_needle。当N_needle=1时，几乎任何算法都是O(N_haystack)。大多数算法都是O(N_haystack * N_needle) 或更快，而且你可以假设N_needle <= C。 - MSalters

Answer 2

使用 std::string::find。你可以这样做:

std::string::size_type start_pos = 0;
while( std::string::npos != 
          ( start_pos = mystring.find( my_sub_string, start_pos ) ) )
{
    // do something with start_pos or store it in a container
    ++start_pos;
}

编辑：哎呀！感谢Nawaz的提醒！更好了吗？

- Kiril Kirov

---

好了。但是现在，你需要在循环中使用 if-else 吗？ - Nawaz

哈，不错 :) 当我还半睡半醒时就会发生这种情况 :D 不，我不需要它。只是第一次，我认为如果 my_sub_string 只是一个字母，放在 mystring 的末尾，没有它可能会漏掉最后一个字符。再次感谢！ - Kiril Kirov

那看起来比之前好了... +1 - Nawaz

Answer 3

我为了完整性而补充，还有另一种方法可以使用 std::search，它类似于 std::string::find，但是区别在于您需要使用迭代器，示例如下：

std::string::iterator it(str.begin()), end(str.end());
std::string::iterator s_it(search_str.begin()), s_end(search_str.end());

it = std::search(it, end, s_it, s_end);

while(it != end)
{
  // do something with this position..

  // a tiny optimisation could be to buffer the result of the std::distance - heyho..
  it = std::search(std::advance(it, std::distance(s_it, s_end)), end, s_it, s_end);
}

我发现这种方法有时比std::string::find更有效，特别是当你将字符串表示为一个vector<char>时。

- Nim

Answer 4

只需使用std::string::find()，它返回找到子字符串的位置，如果没有找到，则返回std::string::npos。

这里是文档。

下面是从该文档中提取的示例：

// string::find
#include <iostream>
#include <string>
using namespace std;

int main ()
{
  string str ("There are two needles in this haystack with needles.");
  string str2 ("needle");
  size_t found;

  // different member versions of find in the same order as above:
  found=str.find(str2);
  if (found!=string::npos)
    cout << "first 'needle' found at: " << int(found) << endl;

  found=str.find("needles are small",found+1,6);
  if (found!=string::npos)
    cout << "second 'needle' found at: " << int(found) << endl;

  found=str.find("haystack");
  if (found!=string::npos)
    cout << "'haystack' also found at: " << int(found) << endl;

  found=str.find('.');
  if (found!=string::npos)
    cout << "Period found at: " << int(found) << endl;

  // let's replace the first needle:
  str.replace(str.find(str2),str2.length(),"preposition");
  cout << str << endl;

  return 0;
}

- ereOn

---

@sehe：在链接的文档中有一个（我现在已经重新复制了）。显然有点晚了 ;) - ereOn