C - check if string is a substring of another string

Question

I need to write a program that takes two strings as arguments and check if the second one is a substring of the first one. I need to do it without using any special library functions. I created this implementation, but I think it's always returning true as long as there is one letter that's the same in both strings. Can you help me out here. I'm not sure what I am doing wrong:

#include <stdio.h>
#include <string.h>

int my_strstr( char const *s, char const *sub ) {
    char const *ret = sub;

    int r = 0;
    while ( ret = strchr( ret, *sub ) ) {
        if ( strcmp( ++ret, sub+1 ) == 0 ){
            r = 1;
        }
        else{
            r = 0;
        }        
    }
    return r;
}

int main(int argc, char **argv){

    if (argc != 3) {
        printf ("Usage: check <string one> <string two>\n");
    }
    int result = my_strstr(argv[1], argv[2]);

    if(result == 1){
        printf("%s is a substring of %s\n", argv[2], argv[1]);
    } else{
        printf("%s is not a substring of %s\n", argv[2], argv[1]);
    }
    return 0;
}

Solution 1

Your approach to writing strstr is fundamentally flawed. Let's look at what you wrote:

char const *ret = sub;

int r = 0;
while ( ret = strchr( ret, *sub ) ) {
    if ( strcmp( ++ret, sub+1 ) == 0 ){
        r = 1;
    }
    else{
        r = 0;
    }        
}
return r;

First of all, since you initialize ret to point to sub, you are comparing sub against itself, and never looking at s. But let's assume that you meant for ret to be initialized to s...

ret = strchr( ret, *sub ) finds the position of the next character of sub within ret, and then advances ret so that it starts on that character.

Then, you execute strcmp( ++ret, sub+1 ) which determines if the string beginning from the next character of ret is equal to the string beginning from the next character of sub, and then advances ret to start with the next character (regardless of whether the test was true or false).

Clearly, this logic isn't doing what you want. What it will actually do is determine if the substring is either equal to the string s or is found at the end of the string s and includes no repeated letters.

Here's a general outline of the algorithm you want:

1. Find the position of the first character of sub in s. If not found, return false.
2. Update s so that it starts at this position
3. Assuming the length of sub is n, test if the first n characters of s match sub (being careful not to run past the end of s). If so, return true. Otherwise, advance s by one character and loop.

Note that you should never be searching for any character in sub other than the first. The idea is to use the first character of sub to find potential starting positions for sub in s, and then check if the substring sub actually exists there. If it isn't there, you want discard the entirety of s up to that point, and then start over by trying to find the next potential starting position.

Solution 2

Well, you shouldn't be modifying ret in my_strstr. And strcmp does not compare substrings, it compares strings. You probably want to use strncmp.