6
\$\begingroup\$
int FindStr(char* str, int strsize, char* fstr, int from)
{
    for(int i=from, j=0; i<strsize; i++)
    {
        if(str[i]==fstr[j])
            j++;
        else
            {i-=j; j=0;}

        if(fstr[j]=='\0')
            return i-j+1;
    }

    return -1;
}

The function searches for a string fstr in str and returns its index in str if found, otherwise, it will return -1. It's also possible to specify where to start searching in the string.

My question is, can I optimize this function further? Also, do you see any potential problems in this function?

\$\endgroup\$
0

3 Answers 3

4
\$\begingroup\$

Some comments to add to the first two of @200_success:

  • strstr does a good job. Why reinvent?

  • sizes are often passed as size_t rather than int

  • modifying the loop variable within the loop is generally considered bad practice

  • i -= j executes on every loop unless there is a match. Mostly in this case j is zero so the line has no effect, but it still executes

  • if fstr is an empty string it returns the wrong result (1)

  • add some spaces around operators and after if, for

\$\endgroup\$
4
  • \$\begingroup\$ Reinvention is just due to curiosity. Why is loop variable modification bad practice? What if you know what you're doing? As for i-=j; I think if(j>0){i-=j; j=0;} would cut down on the redundant assignments, but is that going to improve its performance? \$\endgroup\$
    – Hex4869
    Commented Dec 29, 2013 at 4:53
  • 1
    \$\begingroup\$ Its not the compiler or the machine you write your code for. It is the next poor slub who has to come along and maintain and fix it. You may know what you are doing. But the next person who looks at the code does not know that you know what you are doing. Writing code that modifies the loop variable is never easy to understand. Writing it a slightly longer way that is easy to read will be unlikely to affect straight line speed. But will make it a thousand times faster to understand and thus fix. If you really know what you are doing then you write 5 paragraphs explaining each optimization :-) \$\endgroup\$ Commented Dec 29, 2013 at 6:25
  • \$\begingroup\$ What you have done here is optimized away an inner loop in the source code. But effectively left it in the machine instructions. The i-=j is basically an inner loop reset. So you have gained no significant speed advantage but made the code much harder to read. \$\endgroup\$ Commented Dec 29, 2013 at 6:32
  • \$\begingroup\$ Yes, that's something I need to keep in mind. I always write code without thinking about how other people will perceive it. I need to pay more attention to that. Thanks! \$\endgroup\$
    – Hex4869
    Commented Dec 30, 2013 at 14:56
3
\$\begingroup\$

Why is fstr treated as a null-terminated string, while the size of str has to be explicitly passed in?

What is the expected behaviour when searching for an empty string?

This is a pretty good simple string search. There are more sophisticated algorithms that try to avoid backtracking.

\$\endgroup\$
3
  • \$\begingroup\$ Well, I thought that if I want to traverse the string, I'm going to either have to check on each iteration if the end of the string is reached or search for the null-termination and find the size from there. Having the size makes it easier. Having the size of fstr can also help by simplifying the second if statement, now that I think of it. \$\endgroup\$
    – Hex4869
    Commented Dec 28, 2013 at 18:49
  • 2
    \$\begingroup\$ Checking for str[i] != '\0' is just as easy as checking for i < strsize. Null-terminated strings produce a much more natural interface. Furthermore, requiring an explicit strsize might force the caller to call strlen() first, which is O(n). On the other hand, you have to traverse the string anyway in FindStr(), so you get that work for "free". \$\endgroup\$ Commented Dec 28, 2013 at 19:07
  • \$\begingroup\$ Yeah, checking for the null-termination does look better and eliminates the the size parameter. The part about strlen() too. \$\endgroup\$
    – Hex4869
    Commented Dec 29, 2013 at 4:43
0
\$\begingroup\$

I'm assuming you don't want to use the string library.

The header for FindStr should be as follows:

char *FindStr(const char *str, const int strsize, const char *fstr, const int from)

You should return a pointer to the char where the substring is, if it is found, or NULL otherwise. There's no reason for FindStr to modify the arguments, so declare them const.

\$\endgroup\$
3
  • \$\begingroup\$ Is there any advantage to using const other than making it clear to the person reading the code that these variables can't be modified? \$\endgroup\$
    – Hex4869
    Commented Dec 30, 2013 at 14:58
  • \$\begingroup\$ @Hex4869 You can pass a string literal into str and fstr if they are const. \$\endgroup\$
    – jliv902
    Commented Dec 30, 2013 at 18:01
  • \$\begingroup\$ @Hex4869 It'll prevent you or somebody else who modifies the code later from making a mistake and modifying a value that shouldn't be modified. You may forget or make a mistake. \$\endgroup\$ Commented Dec 30, 2013 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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