计算字符串中子字符串的所有出现次数的最佳方法是什么?
示例:计算
Foo
中
FooBarFooBarFoo
的出现次数
一种方法是使用 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;
}
#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;
}
您应该为此使用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/
#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;
}
#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;
}
在我的软件中,我正在使用此函数(使用嵌套迭代器):
int Global::count (const std::string& str, const std::string& substr) {
int nocc (0);
if (substr.begin () == substr.end ()) {
// error ("count : empty substr");
}
if (substr.size () <= str.size ()) {
const auto ssiz (substr.size ());
auto i0 (substr.begin ()), j0 (substr.end ()), k0 (i0);
auto i (str.begin ()), k (i);
auto end (str.end ());
end -= ssiz;
auto c0 (*substr.begin ());
std::for_each (str.begin (), str.end (), [&c0, &nocc, &i, &i0, &j0, &k0, &k] (const auto& c) {
if (c == c0) {
k0 = i0; k = i;
for (; k0 != j0; ++k0, ++k) {
if (*k0 != *k) break;
}
if (k0 == j0) ++nocc;
}
++i;
});
}
return nocc;
}
用途:
#include <string>
#include "Global.hpp"
int main (int argc, char* argv []) {
int nocc (0);
std::string str ("FooBarFooBarFoo"), substr ("Foo");
nocc = Global::count (str, substr);
std::cout << "nocc == " << nocc << std::endl;
}