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

2022-01-20 00:00:00 string find c++

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

I want to search a large string for all the locations of a string.

推荐答案

另外两个答案是正确的，但是它们非常慢并且具有 O(N^2) 复杂度.但是有 Knuth-Morris-Pratt 算法，以 O(N) 复杂度查找所有子字符串.

The two other answers are correct but they are very slow and have O(N^2) complexity. But there is the Knuth-Morris-Pratt algorithm, which finds all substrings in O(N) complexity.

此外，还有另一种算法:所谓的Z 函数"；复杂度为 O(N)，但我找不到该算法的英文源代码(可能是因为还有另一个更著名的同名算法 - Rieman 的 Z 函数)，所以我将其代码放在这里并解释它的作用.

Also, there is another algorithm: the so-called "Z-function" with O(N) complexity, but I couldn't find an English source for this algorithm (maybe because there is also another more famous one with same name - the Z-function of Rieman), so I will just put its code here and explain what it does.

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
}

相关文章