2
\$\begingroup\$

I have written a program, in which I have to find the number of occurrences (overlapping + non-overlapping) of a string in another string.

// variable to keep track of word
int i=0;
for(vector<string>::iterator it = p.begin(); it!=p.end(); it++){
    frequency[i]=0;
    int start=0;
    while(true){
        start = s.find(*it, start);

        if(start==-1){  // not found
            break;
        } else{
            frequency[i]++;
            start++;
        }
    }

    i++;
}

I am finding the starting index start of the match, and then again searching for the string starting from 'start+1' this time, and so on. The length of the string s, in which searching has to be performed is 50,00,000. And total number of keywords (stored in vector p here) is 500 (each having length of 5000).

\$\endgroup\$
  • \$\begingroup\$ What exactly are you looking to improve? Or are you looking for a general review? \$\endgroup\$ – svick Aug 11 '13 at 12:35
3
\$\begingroup\$

I don't like nested loops. They are generally unnecessry and are often confusing. So instead of your two loops, I would extrac the inner loop to a function, for example:

int key_search(const std::string& s, const std::string& key)
{
    int count = 0;
    size_t pos=0;
    while ((pos = s.find(key, pos)) != std::string::npos) {
        ++count;
        ++pos;
    }
    return count;
}

This searches the inputs string s for occurances of string key and returns the number of matches. A few things are worth noting:

  • The parameters are passed as const references - const because you don't change them and references for efficiency.

  • I used string::npos as the idicator of failure from strings find method, instead of -1 (-1 would give a warning from the compiler if you have sign conversion warnings enabled).

  • I didn't use a while(true) loop but instead used the return from s.find directly to control the loop.

  • I pre-incremented variables instead of post-increment (++pos, not pos++) which can be more efficient (although with built in types it makes no difference).

  • pos (your start) is of type size_t, not int. Or you could use std::string::size_type, which is the also size_t.

  • It is normal to prefix your use of standard library things with std::, so string becomes std::string etc.

The main loop now just needs to call key_search

int i = 0;
for (auto it = keys.begin(); it != keys.end(); ++it){
    frequency[i] = key_search(s, *it);
    ++i;
}

With C++11 you can use auto to simplify the iterator definition. You don't show what frequency is, but I'm assuming it is an array (which are generally best avoided in C++).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.