如何查找字符串中的子字符串的所有位置？ [英] How do i find all the positions of a substring in a string?

问题描述

解决方案

我想要搜索一个大字符串来查找字符串的所有位置。另外两个答案是正确的，但是它们非常慢并且具有O（N ^ 2）复杂度。但有 Knuth-Morris-Pratt 算法可以找到所有子字符串

还有另一种算法所以称为Z函数与O（N）复杂性，但我找不到这个算法的英语源（也许因为还有另一个更有名的东西具有相同的名称 - Riman的Z函数），所以将只是将其代码放在这里并解释它的工作。

  void calc_z（string& s，vector< int>& 
 {
 int len = s.size（）; 
 z.resize（len）; 
 
 int l = 0，r = 0; 
 for（int i = 1; i  if（z [i-1] + i <= r）
 z [i] = z [i-1] 
 else 
 {
 l = i; 
 if（i> r）r = i; 
 for（z [i] = ri; r  if（s [r]！= s [z [i]]）
 break; 
 --r; 
} 
} 
 int main（）
 {
 string main_string =一些字符串，我们想要查找子字符串或子字符串或只是sub; 
 string substring =sub; 
 string working_string = substring + main_string; 
 vector< int> z; 
 calc_z（working_string，z）; 
 
 //此后z [i]是working_string的前缀的最大长度
 //等于从
 // working_string的第i个位置开始的字符串。因此，z [i]> = substring.size（）
 //的位置是子串的位置。 
 
 for（int i = substring.size（）; i< working_string.size（）; ++ i）
 if（z [i] ）
 cout<< i-substring.size（）< endl; // to get position in main_string 
} 
  

How would i go about this?I want to search a large string for all the locations of a string.

解决方案

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

edit:

Also there is another algoritm so called "Z-function" with O(N) complexity, but I couldn't find English source of this algorithm (maybe because there is also another more famouse thing with same name - the Z-function of Riman), so will just put its code here and explain what it do.

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
}

这篇关于如何查找字符串中的子字符串的所有位置？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！