CODEWITHSUNDEEP
c++string
SomeName
SomeName

Reputation: 969

The best way to find number of occurrences of word in string (C++, no spaces in string)

Let's say you are given a string "banana".

You want to find out how many times "ana" can be found in "banana". So, that number is 2.

string s = "banana";
int num = 0,pos = 0;
pos = s.find("ana");
while(pos!=string::npos) {
    num++;
    pos = s.find("ana",pos+1);
}
cout<<num<<endl;

The thing is, I want to write shorter code for this. What functions can be used ? I tried using search() but it's not what I wanted. Count() is only for characters.

Are there any other functions that can help me with doing this ? (Boost is not allowed on competitions, so not this one).

Upvotes: 1

Views: 708

Answers (4)

AKL
AKL

Reputation: 1389

Assuming that finally you intend to also count any possible replication of a phrase, here are 3 generic function templates which work for almost any container or pointer/array , providing that they are given the right first/last iterator instead of container!

#include <iterator>
#include <algorithm>
#include <map>
#include <vector>

//finding the occurrence for an specific case within a range
template<typename rng_t__, typename dif_t__ = typename std::iterator_traits<rng_t__>::difference_type>
dif_t__ occurrence(const rng_t__ rng_fst_, const rng_t__ rng_lst_, const rng_t__ schd_fst_, const rng_t__ schd_lst){
    dif_t__ counter = 0;
    for (rng_t__ it = rng_fst_; (it = std::search(it, rng_lst_, schd_fst_, schd_lst))++ != rng_lst_; ++counter);
    return counter;
}
//finding the replications for all subsets with certain length within a range
template<typename rng_t__, typename dif_t__ = typename std::iterator_traits<rng_t__>::difference_type, typename val_t__ = typename std::iterator_traits<rng_t__>::value_type>
dif_t__ replications(const rng_t__ rng_fst_, const rng_t__ rng_lst_, dif_t__ lnt_){
    if(!lnt_ or lnt_ >= std::distance(rng_fst_, rng_lst_)) return 0;
    rng_t__ it_lst = rng_fst_;
    for (--lnt_; lnt_--; ++it_lst);
    std::map<std::vector<val_t__>, dif_t__> cases;
    for (rng_t__ it_fst = rng_fst_; it_lst++ != rng_lst_; ++it_fst){
        auto it_rslt_pair = cases.insert({{it_fst, it_lst}, 0});
        if(! it_rslt_pair.second) ++(it_rslt_pair.first->second);
    }
    dif_t__ counter = 0;
    for (const auto& a_case : cases) counter += a_case.second;
    return counter;
}
//finding the replications for all subsets with all possible lengths within a range
template<typename rng_t__, typename dif_t__ = typename std::iterator_traits<rng_t__>::difference_type, typename val_t__ = typename std::iterator_traits<rng_t__>::value_type>
dif_t__ replications(const rng_t__ rng_fst_, const rng_t__ rng_lst_){
    const dif_t__ rng_lnt = std::distance(rng_fst_, rng_lst_);
    dif_t__ counter = 0;
    for (dif_t__ a_lnt = 0; ++a_lnt < rng_lnt; counter += replications(rng_fst_, rng_lst_, a_lnt));
    return counter;
}

#include <string>

int main(int argc, char** argv) {

    std::string range = "banana", searched = "ana";

    std::cout<< "total occurrence for the ana" << std::endl;
    std::cout<< occurrence("banana", "banana" + 6, "ana", "ana" +3) << std::endl;
    std::cout<< occurrence(range.begin(), range.end(), searched.begin(), searched.end()) << std::endl;

    std::cout<< "total replications for every phrase from banana with length of 3" << std::endl;
    std::cout<< replications("banana", "banana" + 6, 3) << std::endl;
    std::cout<< replications(range.begin(), range.end(), 3) << std::endl;

    std::cout<< "total replications for every phrase from banana with every possible length" << std::endl;
    std::cout<< replications("banana", "banana" + 6) << std::endl;
    std::cout<< replications(range.begin(), range.end()) << std::endl;

    return 0;
}

possible output:

total occurrence for the ana
2
2
total replications for every phrase from banana with length of 3
1
1
total replications for every phrase from banana with every possible length
6
6

Good luck with the competition!

Upvotes: 1

Alan Birtles
Alan Birtles

Reputation: 36379

Probably the simplest code without sacrificing readability is something like this:

std::string s = "banana";
int num = 0;
size_t pos = 0;

while ((pos = s.find("ana", pos)) != std::string::npos)
{
    num++;
    pos++;
}
std::cout << num << "\n";

or as a for loop:

std::string s = "banana";
int num = 0;
for (size_t pos = 0; (pos = s.find("ana", pos)) != std::string::npos; num++, pos++)
{
}
std::cout << num << "\n";

Upvotes: 0

mch
mch

Reputation: 9804

You can use a for loop for this:

string s = "banana";
int num = 0;

for (auto pos = s.find("ana"); pos != string::npos; pos = s.find("ana",pos+1))
    num++;
cout << num << endl;

As you can see, I used auto as type for pos, so it will have the correct type std::string::size_type.

Upvotes: 0

Paul Evans
Paul Evans

Reputation: 27567

I want to write shorter code for this

You want to use while (true) and break:

std::string s{"banana"};
std::string::size_type pos{0};
int num{0};
while (true) {
    pos = s.find("ana", pos);
    if (pos == std::string::npos) break;
    pos += 2; // next possible place for an "ana";
    ++num;
} 
std::cout << num << "\n";

Upvotes: 0

Related Questions