2
\$\begingroup\$

I'm trying to implement a function to determine if a substring is indeed a substring of a string s.

This is what I came up with but I feel that there must be elegant way.

#include <iostream>

bool isSubstr(std::string s, std::string sub) {
    if (s.size() < sub.size()) { return false; }
    for (int i = 0; i <= s.size() - sub.size(); i++) { // for every start index in s
        int start = i;
        for (int j = 0; j < sub.size(); j++) { // check that if sub matches starting at that index
            if (s[start++] != s[j]) {
                break;
            }
        }
        if (start == sub.size() && s[start - 1] == s[sub.size() - 1]) {
            return true;
        }
    }
    return false;
}

int main() {
    printf("h is a substring of hello? %d\n", isSubstr("hello", "h"));
    printf("lo is a substring of hello? %d\n", isSubstr("hello", "lo"));
    printf("he is a substring of hello? %d\n", isSubstr("hello", "he"));
    printf("hello is a substring of hello? %d\n", isSubstr("hello", "hello"));
    printf("heo is a substring of hello? %d\n", isSubstr("hello", "heo"));
    printf("ho is a substring of hello? %d\n", isSubstr("hello", "ho"));
    printf("helloworld is a substring of hello? %d\n", isSubstr("hello", "helloworld"));
}
\$\endgroup\$
  • \$\begingroup\$ The first "if" is unnecessary, it is repeated in the "for" test, s.size() - sub.size() <0. You could replace the inner loop with strncmp. \$\endgroup\$ – QuentinUK Mar 12 '15 at 0:48
  • 2
    \$\begingroup\$ Is this for educational purposes, or why don't you use std::string::find or std::search? \$\endgroup\$ – dyp Mar 12 '15 at 0:48
3
\$\begingroup\$

Bugs!

There is a bug in this. It prints 1 for "heo" and "he", which should both print 0. Note that if start == sub.size() then s[start - 1] == s[sub.size() - 1] is always true. Perhaps you meant s[start - 1] == sub[sub.size() - 1].

Also, if (s[start++] != s[j]) { should probably be if (s[start++] != sub[j]) {.

std::find

The simplest form of this would be something like

bool isSubstr(std::string s, std::string sub) {
    return s.find(sub) != std::string::npos;
}

Since std::find returns the position in the string, we have to check that the position is not valid to convert to a boolean value.

Reinventing the wheel

A better version if you want to roll your own would be

bool isSubstr(std::string s, std::string sub) {
    std::size_t length = s.size(), sub_length = sub.size();
    int max_start = length - sub_length;

    for (int start = 0; start <= max_start; start++) {
        if ( 0 == s.compare(start, sub_length, sub) ) {
            return true;
        }
    }

    return false;
}

Notice how using compare allows for a simpler inside. This would be true even if you had to roll your own compare:

int compare(int start, std::string a, std::string b) {
    for ( int i = 0, end = b.size(); i < end; ++i ) {
        if ( a[start + i] != b[i] ) {
            return false;
        }
    }

    return true;
}

which would be used like

        if ( compare(start, s, sub) ) {

Note how adding the function saves the extra if in isSubstr that you used.

Note how I get the string sizes first and store them in variables. This avoids the overhead of function calls. Your version had at least two function calls per iteration. Mine only has one, and that one allows for simpler code (that avoids two more function calls). I also avoid doing a subtraction for every iteration.

On the bright side, in your version the function calls probably get optimized out. Mine won't be because I use a loop in that function.

C

You use the C printf. If you wanted to use the C string functions as well, you could say:

bool isSubstr(std::string s, std::string sub) {
    std::size_t length = s.size(), sub_length = sub.size();
    int max_start = length - sub_length;

    for (int start = 0; start <= max_start; start++) {
        if ( 0 == strncmp(s.c_str() + start, sub.c_str(), sub_length) ) {
            return true;
        }
    }

    return false;
}

No compare function

If performance is so important that you don't want to make any function calls in the loop, then

    for (int j = 0; j < sub.size(); j++) { // check that if sub matches starting at that index
        if (s[start++] != s[j]) {
            break;
        }
    }
    if (start == sub.size() && s[start - 1] == s[sub.size() - 1]) {
        return true;
    }

could become

    bool is_match = true;
    for (int j = 0; j < sub.size(); j++) { // check that if sub matches starting at that index
        if (s[start++] != sub[j]) {
            is_match = false;
            break;
        }
    }

    if (is_match) {
        return true;
    }

This explicitly marks when it exits the inner loop early rather than trying to recalculate it. This pattern tends to be more robust at the cost of an extra variable. However, there's a good chance that the compiler can optimize out that variable.

This is also one of the times that a goto can be considered valid in C/C++. Other languages use labeled break and continue statements to get the same effect.

\$\endgroup\$
2
\$\begingroup\$

It's good that this is a reasonable runtime and reasonably efficient. I also like that you're not using using namespace std. There are, however, a few things I noticed that haven't already been addressed.

Technicalities

  • Since you don't modify either s or sub, both should be taken by const reference. Currently your function creates unnecessary copies since the variables are taken by value.
  • You're missing the string include.
  • iostream doesn't include printf. You need the cstdio header (which will mean it should be std::printf instead of printf).

Style

  • As already mentioned by dyp, tinstaafl, and dyp, you're way over complicating this. You should just use string::find.
  • I would use i + j instead of start.
  • isSubstr is a questionable name. It can obviously be interpreted as "is a a substring of b", but I think contains would be clearer.

Other options

Assuming this is an assignment for which you were told that you can't use string::find and you wanted to be a smart ass, you can implement this in one line with std::search (in fact, std::search is just a container-agnostic version of find).

bool contains(const std::string& haystack, const std::string& needle) {
    return std::search(haystack.begin(), haystack.end(), needle.begin(), needle.end()) != haystack.end();
}
\$\endgroup\$
1
\$\begingroup\$

As has been mentioned using Find would be much more elegant:

string test1 = "abcdefg";
//Since Find returns the index or -1, adding 1 will convert to typical bool values.
//0 for false and any positive integer for true.
bool isSubstr = (bool)(test1.find("abc", 0) + 1);
\$\endgroup\$
  • \$\begingroup\$ find is definitely the correct solution, but the 0 param is unnecessary, and bool isSubstr = (str.find("abc") > -1); is much cleaner. \$\endgroup\$ – Corbin Mar 12 '15 at 3:55

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.