Thread: Finding incidence of one string within another

I've just done a C exercise from a book, the object of which was to write my own version of a function which returns a pointer to the first incidence of one string within another, or NULL if there is no match. It works, but I just get the feeling it's bloated and could be a lot neater. In particular I'm unhappy about the levels of nesting in the function. Should I be? Any advice? My apologies for the indentation, I used tabs and I couldn't work out how to quickly change tab indents to spaces in Visual Studio C++ for posting to a forum.

Code:

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

char * string_in(char * str1, char * str2);


int main(void)
{
	char string[200];
	char match_string[200];
	char * result;
	

	printf("Enter a string to search: ");
	while (gets(string) && string[0] != '\0')
	{
		printf("Enter a string to search for: ");
		do
		{
			if (strlen(gets(match_string)) > strlen(string))
				printf("\nMust not exceed length of first string. Try again: ");
		}
		while (strlen(match_string) > strlen(string));

		result = string_in(string, match_string);

		if (result)
			printf("String was found at position %d", (result - string + 1));
		else
			printf("String was not found.\n\n");
		printf("\nEnter another string to search: ");
	

	}

	return 0;
}

char * string_in(char * s1, char * s2)
{
	char first_ch = s2[0];
	int i, j, match = 0;
	int len_s1 = strlen(s1);
	int len_s2 = strlen(s2);


	for (i = 0; i <= (len_s1 - len_s2); i++)
	{
		if (s1[i] == first_ch)
		{
			match = 1;
			for (j = 1; j < len_s2; j++)
			{
				if (s1[i + j] != s2[j])
				{
					match = 0;
					break;
				}
			}
		}
		if (match == 1)
			break;
	}

	if (match == 1)
		return (s1 + i);
	else
		return NULL;
}

Originally Posted by Sharke

It works, but I just get the feeling it's bloated and could be a lot neater.

I get the same feeling. The nesting is fine, but think: you can return from the middle of the function on the first match, or just return NULL by default at the end if there was no match. So you don't need the boolean flag (int=0 or 1)...you just need your "breaks" and "returns" in the right places.

Originally Posted by itCbitC

AFAICT, there's a lot you can prune from string_in(). Note reaching the end of s2 means it matched so you can use that instead of the inner loop to return from the function.

The OP might, in fact, want to be sure some boundaries are not exceeded in this, although I guess just peeking over the edge won't hurt.

[edit] Nevermind that won't happen...what have I been thinking

I don't mean to sound like an idiot here, but how can I get by without an inner for loop if the full string has to be matched? The outer loop iterates through each letter of s1...now when a letter of s1 matches the first letter of s2, then surely we have to iterate through the letters of s2 in order to see if they all match in sequence within s1?

Just to clarify here - I'm doing this without any external string functions (except strlen). However it didn't specify this in the question and I've just come across the author's solution online:

Code:

#include <string.h>
char * string_in(const char * s1, const char * s2)
{
    int l2 = strlen(s2);
    int tries;            /* maximum number of comparisons    */
    int nomatch = 1;    /* set to 0 if match is found        */
    
    tries = strlen(s1) + 1 - l2;
    if (tries > 0)
        while (( nomatch = strncmp(s1, s2, l2)) && tries--)
            s1++;
    if (nomatch)
        return NULL;
    else
        return (char *) s1;  /* cast const away */
}

But I set out to do it without strncmp of course - I had thought it was an exercise in writing a function from scratch!

Good catch! I did make a booboo and here's the updated one.

Code:

char *string_in(char *s1, char *s2)
{
    int i,j;

    for (i=j=0; s1[j]; j++) {
        if (s2[i] != s1[j])
            i = 0;
        else
            if (!s2[++i])
                return (s1+j+1-i);
    }
    return NULL;
}

I note that this:

Code:

if (s2[i] == s1[j])
    if (!s2[++i])
        return (s1+j+1-i);

can be simplified to:

Code:

if (s2[i] == s1[j] && !s2[++i])
    return (s1+j+1-i);