Find substring in a string

Question

Here is my code to find substring entered by the user in the given string.

bool find_str(char *str, char const *substr) {
    while(*str) {
        if(*str++ == *substr) {
            char const *a = substr;
            while((*str++ == *++a));  /*empty*/
            if(*a == '\0')
                return true;
        }
    }
    return false;
}
// If match found, then return true, else false

int main(void) {
  printf("%d", find_str("ABCDEF", "CDE"));  /* Return true in this case */
  printf("%d", find_str("ABCDE", "CDE")); /* Return false in this case */

}

As explained in the comment, it returns true whenever it ends with an additional characters. If it is not, then it returns false. I think there is a problem in increment/decrement operator. But I could not find how?

*str++, *++a, got me reaching scratching my head trying to remember operator precedence. I don't like remembering things. Either comment it or add some brackets (). — John3136
– John3136, Commented May 13, 2013 at 2:06
Here how it works, first it compare A with C, then with B with C until C == C, so in the nested while it increment with a side-effect making D == D and E == E.(*++a first point to D, whereas *str++ also point to D but increment after) — Ashish Rawat
– Ashish Rawat, Commented May 13, 2013 at 2:07
This is not a code review site. Anyway, strstr does this - 10 seconds google-foo and you can find implementations e.g. opensource.apple.com/source/xnu/xnu-792.13.8/libsa/strstr.c . In your code, there's several bugs: to learn to find them, I recommend putting trace like printf("'%s' =?= '%s'\n", str, a); where you're doing your comparisons... you'll pretty soon see what you're really comparing and realise what's wrong, then you can reason and experiment to fix it. Hint: as Apple did, keep the is-the-a-match-here logic separate from look-everywhere-along-str: strncmp. — Tony Delroy
– Tony Delroy, Commented May 13, 2013 at 2:17

Sergey Kalinichenko · Accepted Answer · 2013-05-13 02:06:18Z

4

This is because your code decides to stop on finding \0 only after performing the comparison

*str++ == *++a

This condition will be true even when the match happens at the end of the string on null terminators, so the while loop would happily proceed beyond the end of both strings past the null terminator, causing undefined behavior.

Changing the condition to exit when *a is zero should fix the problem:

while((*str++ == *++a) && (*a));

answered May 13, 2013 at 2:06

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ashish Rawat Over a year ago

Thanks for debugging, it was so simple

Michael Burr Over a year ago

@ashish2expert: As an aside (and prompted by the @John3136 comment), I think a slight change would make this more easy to read for most programmers: char const *a = substr+1; while(*a && (*str++ == *a++)) {};

asio_guy · Accepted Answer · 2013-05-13 02:32:47Z

I analysed you piece of code a little bit and based on my analysis, I think the problem is in here

        while((*str++ == *++a));    /*empty*/

perhaps you would like to add another statement like below

while((*str++ == *++a) && ( *a != '\0' ) ) ;    /*empty*/

I guess you are missing a null check, what if both pointer are pointing to NULL termination they will still go forward that's exactly whats happening

I was going through your piece of code and found quite a few interesting things

Lets say the memory allocated for CDE is at X
say again the memory allocated for ABCDEF is at X+4 (this was the case in my machine)
and say memory block allocated for ABCDE is at some X+Y or what ever

now when the function is called second time both pointers a and str point to respective memory locations starting at X+2 where Character C satisfies the condition above, however the condition will still be true even if they reach to end i.e at X+3 and hence a will move forward and point to A which makes your program behave erroneously

Collectives™ on Stack Overflow

Find substring in a string

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related