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;
}

Answer 1

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.

Answer 2

It looks like you are searching for char *sub in char * sub:

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

shouldn't you be setting ret to s?

Also strcmp compares strings, not sub strings so strcmp("abcde", "abc") returns false. You probably want strncmp which also takes an integer specifying the length.

Answer 3

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.

Answer 4

When

ret = strchr( ret, *sub )

is first encountered, ret == sub. So, strchr(ret, *sub) is searching the first occurrence of the first char of ret in ret. Which will return ret.

So, ret remains unchanged.

Next,

strcmp( ++ret, sub+1 ) == 0 

ret is still equal to sub, so the above statement is true.

And you get 1 as return.

Answer 5

It may help to break this task down a bit differently. There are two key parts to this task: 1) finding the starting point of potential sub-string matches and 2) testing whether that starting point is indeed a matching sub-string. Therefore, implement this as two functions.

First , create a function that determines if two strings are exactly alike. This should be relatively easy to code, just compare first letter with first letter, second with second, etc. If you find two that don't match, return false. If you make it to the end of one of the strings, return true. If you are allowed to use strncmp, then this would simply be (strncmp(a, b, strlen(b)) == 0) (assuming b is always the shorter string).

Second, create a function that loops through a string, looking for a certain letter. Whenever it finds that letter, it calls a function and passes a pointer to that letter in the string. In other words, if you called my_function("This is a sample string", 's'), then the function should walk through the string, find all four instances of the letter 's' and call a function using a pointer to that letter in the string. In this case, the function you will call is the function described in the previous paragraph.

Using this breakdown, you will return "true" as soon as any of the calls to the sub-function return "true", or you will return "false" if you make it to the end of the input string.