在一个字符串中计算另一个字符串出现的次数

Question

如何最好地统计字符串中子串的所有出现次数？

示例：在字符串FooBarFooBarFoo中统计Foo的出现次数。

- MBZ

---

https://dev59.com/n3VC5IYBdhLWcg3wfxM8#1816989 - Cory Kramer

你需要的时间复杂度是什么？O(N^2)可以简单地按照以下答案建议完成。更棘手的部分是以O(N)的时间复杂度完成。 - Aseem Goyal

@aseem：https://dev59.com/questions/xm025IYBdhLWcg3wwYz4#5816029 - Fred Larson

@yararaffoul，这是指向同一页的链接。 - Gary Strivin'

@GaryNLOL 我想那应该是递归。 - Meraj al Maksud

Answer 1

一种方法是使用std::string的find函数：

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

}

- taocp

---

最坏的情况仍然是O(N*M)，是吧？ - Aseem Goyal

@aseem 对不起我回复晚了。在我看来，标准库函数可能已经被优化过了，它们可能使用KMP算法进行模式匹配，这是高效的。但我并不100%确定。 - taocp

重叠出现时会失败。 - user202729

没有库函数进行优化。 - user202729

@user202729 将 pos += target.length(); 替换为 ++pos，以使其适用于重叠区域。 - Kaiyakha

Answer 2

#include <iostream>
#include <string>

// returns count of non-overlapping occurrences of 'sub' in 'str'
int countSubstring(const std::string& str, const std::string& sub)
{
    if (sub.length() == 0) return 0;
    int count = 0;
    for (size_t offset = str.find(sub); offset != std::string::npos;
     offset = str.find(sub, offset + sub.length()))
    {
        ++count;
    }
    return count;
}

int main()
{
    std::cout << countSubstring("FooBarFooBarFoo", "Foo")    << '\n';

    return 0;
}

- sharkbait

Answer 3

你应该使用 KMP算法 来解决此问题。该算法在时间上的复杂度为 O(M+N)，其中M和N是两个字符串的长度。需要更多信息请查看：https://www.geeksforgeeks.org/frequency-substring-string/ KMP算法会搜索字符串模式。当一个模式子串在模式中出现不止一次时，它利用这种特性来提高时间复杂度，即使在最坏情况下也能做到如此。 KMP算法的时间复杂度为O(n). 请访问以下链接了解详细的算法: https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/

- Prateek Sharma

Answer 4

#include <iostream>
#include<string>
using namespace std;
int frequency_Substr(string str,string substr)
{
    int count=0;
    for (int i = 0; i <str.size()-1; i++)
    {
        int m = 0;
        int n = i;
        for (int j = 0; j < substr.size(); j++)
        {
            if (str[n] == substr[j])
            {
                m++;
            }
            n++;
        }
        if (m == substr.size())
        {
            count++;
        }
    
    }
    cout << "total number of time substring occur in string is " << count << endl;
    return count;
}
int main()
{
    string x, y;
    cout << "enter string" << endl;
    cin >> x;
    cout << "enter substring" << endl;
    cin >> y;
    frequency_Substr(x, y);
    return 0;
}

- Moiz Ahmed

---

很好，你已经编写出代码了。你能否也提供一些代码结果呢？ - Marcel Sonderegger

Answer 5

#include<iostream>
#include<string>
using namespace std;
int main()
{
    string s1,s2;
    int i=0;
    cout<<"enter the string"<<endl;
    getline(cin,s1);
    cout<<"enter the substring"<<endl;
    cin>>s2;
    int count=0;
    string::iterator it=s1.begin();
    while(it!=s1.end())
    {
        if(*it==s2[0])
        {
            int x =s1.find(s2);
            string subs=s1.substr(x,s2.size());
            if(s2==subs)
                count++;
        }
        ++it;
    
    }
    cout<<count<<endl;
    return 0;
}

- deep