# Can this FindString function be optimized further, in terms of speed?

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?

• 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

• 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? – Hex4869 Dec 29 '13 at 4:53
• 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 :-) – Martin York Dec 29 '13 at 6:25
• 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. – Martin York Dec 29 '13 at 6:32
• 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! – Hex4869 Dec 30 '13 at 14:56

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.

• 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. – Hex4869 Dec 28 '13 at 18:49
• 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". – 200_success Dec 28 '13 at 19:07
• Yeah, checking for the null-termination does look better and eliminates the the size parameter. The part about strlen() too. – Hex4869 Dec 29 '13 at 4:43

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.

• 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? – Hex4869 Dec 30 '13 at 14:58
• @Hex4869 You can pass a string literal into str and fstr if they are const. – jliv902 Dec 30 '13 at 18:01
• @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. – Fiddling Bits Dec 30 '13 at 18:05