CODEWITHSUNDEEP
c++stringcounting
MBZ
MBZ

Reputation: 27582

Counting the number of occurrences of a string within a string

What's the best way of counting all the occurrences of a substring inside a string?

Example: counting the occurrences of Foo inside FooBarFooBarFoo

Upvotes: 15

Views: 51454

Answers (6)

Saint-Martin
Saint-Martin

Reputation: 316

In my software, I am using this function that does not create temporary strings, equivalent to a previous answer, but using lambda and iterators:

int Global::count (const std::string& str, const std::string& substr) {
    int nocc (0);
    if (substr.begin () == substr.end ()) {
        nocc = -1;
    }
    else 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;
        ++end;
        auto c0 (*substr.begin ());
        std::for_each (str.begin (), end, [&c0, &nocc, &i, &i0, &j0, &k0, &k, &nb, &ssiz
         ] (const auto& c) {
            if (c == c0) {
                nb = 0;
                k0 = i0; k = i;
                for (; k0 != j0; ++k0, ++k) if (*k0 == *k) {++nb;} else break;
                if (nb == ssiz) ++nocc;
            }
            ++i;
        });
    }
    return nocc;
}

Usage :

#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;
}

Upvotes: 0

deep
deep

Reputation: 1

#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;
}

Upvotes: 0

Moiz Ahmed
Moiz Ahmed

Reputation: 11

#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;
}

Upvotes: 1

Prateek Sharma
Prateek Sharma

Reputation: 372

You should use KMP Algorithm for this. It solves it in O(M+N) time where M and N are the lengths of the two strings. For more info- https://www.geeksforgeeks.org/frequency-substring-string/

So what KMP Algorithm does is, it search for string pattern. When a pattern has a sub-pattern appears more than one in the sub-pattern, it uses that property to improve the time complexity, also for in the worst case.

The time complexity of KMP is O(n). Check this out for detailed algorithm: https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/

Upvotes: 4

taocp
taocp

Reputation: 23624

One way to do is to use std::string find function:

#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;

}

Upvotes: 20

sharkbait
sharkbait

Reputation: 3040

#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;
}

Upvotes: 7

Related Questions