Check if a string is the substring of another string

Question

I was having some problem when trying to check if a string is the substring of another string. Here is the expected output:

Enter a source string: abc
Enter the target string: abcde
findSubstring(): 1

Enter a source string: abcde
Enter the target string: cdef
findSubstring(): -1

And here is my code which used the strstr standard string library:

int main()
{
    char sourceStr[40], targetStr[40];

    printf("Enter a source string: ");
    gets(sourceStr);
    printf("Enter the target string: ");
    gets(targetStr);
    printf("findSubstring(): %d\n", findSubstring(sourceStr, targetStr));
    return 0;
}

int findSubstring(char *s, char *t) {
    if (strstr(s, t) != NULL) {
        return 1;
    }
    return 0;
}

With these code, it works perfectly. However, I was told that I am not supposed to use any standard string library, so I was thinking how should I modify it?

Sorry for posting the question with no error but I seriously need a head start, as I googled for quite a while and I still have no idea how to do it.

Thanks in advance.

[Don't use gets](http://stackoverflow.com/questions/1694036/why-is-the-gets-function-so-dangerous-that-it-should-not-be-used) — crashmstr, Sep 28 '15 at 15:04
Sorry but the main function was part of the question as well. I only need to write up the findSubstring part — QWERTY, Sep 28 '15 at 15:05
You probably want to implement a [naïve string matching](http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/StringMatch/naiveStringMatch.htm) algorithm. — Daniel Kamil Kozar, Sep 28 '15 at 15:06
My comment was making no attempt at answering your question, my comment was purely to tell you not to ever use the function `gets()` in any code you write (as the link explains). — crashmstr, Sep 28 '15 at 15:07
It would seem that the task is to implement the strstr() function yourself. Google "how to implement strstr c" seems productive. — Lundin, Sep 28 '15 at 15:08
Write your own version of `strstr()`? It isn't that all that hard. Simplistically, scan through the source string (haystack), looking for the first character of the target string (needle); when you find that, see whether the following characters match the rest of the needle. If so, you're done; if not, move one until there's nothing more to do. — Jonathan Leffler, Sep 28 '15 at 15:08
pick your favorite: http://www-igm.univ-mlv.fr/~lecroq/string/index.html — Guru Prasad, Sep 28 '15 at 15:10
Alright thanks a lot guys! I will try to figure it out soon! — QWERTY, Sep 28 '15 at 15:13

score 1 · Answer 1 · answered Sep 28 '15 at 15:29

The key here is that when working in C, strings do not exist as an actual data structure as they do in, say, C++'s STL (std::string) or Java's String objects.

Instead, you should be treating them as a sequence of individual characters, whose end is denoted by an agreed-upon convention, which in this case is the 'NULL' character, which is the value 0 and can be represented in a string literal using the escaping symbol.

This is why strings are passed around as pointers to char in C, which actually point to the first character in the sequence.

Therefore, you can use pointer arithmetic to check the subsequent characters, until you find a value of 0, which means the string has ended.

By using a snippet like this, you can check any given string character by character.

char * pointer_to_string; //Pointer to start of string
char * pointer_to_character = pointer_to_string; //Start at the first character

while (*pointer_to_character != '\0'){  // Repeat while we haven't found the end
    char c = *pointer_to_character; // The character the pointer is pointing to.
    //do what you need to with the character

    pointer_to_character++; //Now it points to the next character
}
// We exit the loop once the end of the string is found

HOWEVER: This means you must be careful since this kind of string manipulation has its risks, since you are depending on finding an actual NULL character that ends the string, and if it's not present, the loop would run indefinitely, and in more complex examples, would easily lead to a segmentation fault and a crash.

In short, when using raw pointers in C, gotta be extra careful with what you do with the underlying memory, and certainly using known libraries and not reinventing the wheel tends to be the best option, but since I'm inclined to believe the purpose of the assignment is learning about string representation and pointer arithmetic, we'll do with that.

With this, you should be able to figure out what you need to do to solve the problem.

The "*'NULL' character*" actually is called "null-character" or just `NUL` (with one ell only). `NULL` is something different. — alk, Sep 28 '15 at 16:15

machine_1 · Answer 2 · 2015-09-28T18:57:46.783

1

Well, if you don't want to use standard library, here is one way to do it. This is simple code that satisfies the purpose:

int FindString(char *Str,const char *SubStr)
{
    size_t count = 0 , x , y ;
    size_t Str_len = strlen( Str ) ;
    size_t SubStr_len = strlen( SubStr );
    size_t diff = Str_len - SubStr_len;

    if( SubStr_len > Str_len )
        return 0;

    for( x = 0 ; x <= diff ; x++ )
    {
        for( y = 0 ; y < SubStr_len ; y++ )
        {
            if( Str[ x + y ] == SubStr[ y ] )
                count++;
            else
            {
                count = 0;
                break;
            }
        }
        if( count == SubStr_len )
            return 1;
    }
    return 0;
}

Also, if you want the version that compares insensitively, notify me in a comment.

edited Sep 28 '15 at 18:57

answered Sep 28 '15 at 16:21

machine_1

4,266
2
21
42

All `unsigned int` should be `size_t` (see what `strlen()` returns). – alk Sep 28 '15 at 16:22
Interesting code. Note @alk's comment. You carefully keep `count` at the same value as `y`, so you don't actually need `count`; you can test `y` instead. I was originally going to suggest moving `size_t count = 0;` inside the outer for loop (before the start of the inner for loop), but when you observe that `count == y`, you can do without it altogether. You can, therefore, revise/simplify/shorten the inner loop body to `if (Str[x+y] != Substr[y]) break;`. – Jonathan Leffler Sep 28 '15 at 18:37

Check if a string is the substring of another string

2 Answers2