My strstr function works, but a program designed to test it says it doesn't

Question

for school, I have to recreate the strstr function. I did, and I tested it as much as I could, and everything seems to work perfectly.

I am still looking into it but after several hours of troubleshooting, I don't get it. Can someone tell me what's wrong with it compared to strstr ?

char    *ft_strstr(char *str, char *to_find)
{
    int i;
    int k;

    i = 0;
    k = 0;
    if (*to_find == 0)
        return (str);
    while (str[i] != 0)
    {
        while (str[i] == to_find[k])
        {
            i++;
            k++;
            if (to_find[k] == 0)
                return (&str[i - k]);
        }
        i++;
        k = 0;
    }
    return (0);
}

Should I include a main for testing ?

Thank you.

EDIT : Here is the error code of the machine :

> $> ./0z09k44vyodiwxihua4w30m9 $> diff -U 3 user_output_test1
> test1.output | cat -e
> --- user_output_test1   2021-08-11 17:55:47.000000000 +0000$
> +++ test1.output        2021-08-11 17:55:47.000000000 +0000$ @@ -2,7 +2,7 @@$  0$  -1$  0$
> -7$
> +-1$  0$  2$  2$ @@ -12,7 +12,7 @@$  -1$  -1$  -1$
> -87$
> +-1$  -1$  -1$  -1$
> 
> Diff KO :( Grade: 0

Answer 1

These while loops are incorrect

while (str[i] != 0)
{
    while (str[i] == to_find[k])
    {
        i++;
        k++;
        if (to_find[k] == 0)
            return (&str[i - k]);
    }
    i++;
    k = 0;
}

Let's assume that str is "aab" and to_find is "ab". In this case the inner while loop gets the control because str[0] is equal tp to_find[0]. Within the loop the both indices are incremented and str[1] is not equal to to_find[1]. So the loop interrupts its iteration and after the loop the index i is incremented again and becomes equal to 2. So the substring will not be found.

You need to introduce another index for the inner while loop. For example

while (str[i] != 0)
{
    int j = i;
    while (str[j] == to_find[k])
    {
        j++;
        k++;
        if (to_find[k] == 0)
            return (&str[j - k]);
    }
    i++;
    k = 0;
}

In fact you need to use only one variable as an index. The loops can be rewritten like

for ( ; *str; ++str )
{
    size_t i = 0;

    while ( str[i] == to_find[i] )
    {
        if ( to_find[++i] == '\0' ) return str;
    }
} 

Pay attention to that the function has the following declaration

char *strstr(const char *s1, const char *s2);

That is its parameters have the qualifier const.

If you will declare the function this way then the return statement will look like

return ( char * )(&str[j - k]);

or

return ( char * )str;

if to use the modified loops shown above.

Here is a demonstrative program.

#include <stdio.h>

char * ft_strstr( const char *str, const char *to_find )
{
    if ( *to_find == '\0' ) return ( char * )str;
    
    for ( ; *str; ++str )
    {
        size_t i = 0;

        while ( str[i] == to_find[i] )
        {
            if ( to_find[++i] == '\0' ) return ( char * )str;
        }
    }
    
    return NULL;
}

int main(void) 
{
    char *p = ft_strstr( "aab", "ab" );
    
    if ( p ) puts( p );
    
    return 0;
}

The program output is

ab

Answer 2

The main problem is you do not backtrack to the beginning of the match when you have a partial match: your function will not match aab in the string aaab. You can fix this by setting i = i - k + 1; instead of i++; after the inner loop.

Also note that 0 in your code means very different things: the null terminator byte in a string, the number zero as an index, and the null pointer. It would be more readable to use '\0' for the null terminator and NULL for the null pointer.

Furthermore, index variables should have type size_t in case string lengths exceed the range of type int.

Here is a modified version:

char    *ft_strstr(char *str, char *to_find)
{
    size_t i;
    size_t k;

    i = 0;
    k = 0;
    if (*to_find == '\0')
        return (str);
    while (str[i] != '\0')
    {
        while (str[i] == to_find[k])
        {
            i++;
            k++;
            if (to_find[k] == '\0')
                return (&str[i - k]);
        }
        i = i - k + 1;
        k = 0;
    }
    return (NULL);
}

Answer 3

The main problem is that your code needs to compare str to to_find for every starting index in str, until it finds a match. Currently, if your code find a partial match, it will "skip" checking certain starting indices. For example, try the string aab and the substring ab. It will actually result in a segfault.

Some additional advice:

• Look up the exact function definition and behavior on a website like cppreference.
• For i and k; It is better to define and initialize a variable on the same line.
• Be explicit: return NULL (a null pointer) and compare with \0 for the null-terminator.
• When thinking of test cases, do not think of a string and a substring, but of any valid input and how your program will handle it.

Answer 4

Your strstr() doesn't work. I'm having difficulty constructing the counterexample, but if you advance several places through to_find on a false match you don't rewind and start in the next place and try the match again.

As Weather Vane wrote in comments, don't increment i in the inner loop. That's what causes the problem.