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.

Sorry but the main function was part of the question as well. I only need to write up the findSubstring part — QWERTY
– QWERTY, Commented Sep 28, 2015 at 15:05
It would seem that the task is to implement the strstr() function yourself. Google "how to implement strstr c" seems productive. — Lundin
– Lundin, Commented Sep 28, 2015 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
– Jonathan Leffler, Commented Sep 28, 2015 at 15:08
pick your favorite: www-igm.univ-mlv.fr/~lecroq/string/index.html — Guru Prasad
– Guru Prasad, Commented Sep 28, 2015 at 15:10

CFX · Accepted Answer · 2015-09-28 15:29:59Z

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.

machine_1 · Accepted Answer · 2015-09-28 18:57:46Z

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, 2015 at 18:57

answered Sep 28, 2015 at 16:21

machine_1

4,4643 gold badges24 silver badges44 bronze badges

2 Comments

alk Over a year ago

All unsigned int should be size_t (see what strlen() returns).

Jonathan Leffler Over a year ago

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

Collectives™ on Stack Overflow

Check if a string is the substring of another string

2 Answers 2

1 Comment

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related