CareerCup

There are some other interesting cases:

1. When the last unmatched character marks the beginning of the substring, it will fail. For example, let str = "babad" and substr = "bad".
2. More generally, the code does not handle the cases where the last analyzed characters don´t match substr completely but match a prefix of substr. For example: str = "bababd", substr = "babd"

str = "google"
substr = "ler"

If some prefix of substr (but not all), eg 'le', is the suffix of str this algo will not work. It will return there invalid results instead of null

The program would fail for a str , substr where str does not contain substr but the last character would match . The program would still return the address of the last character in str which is incorrect.

str = "abc"
substr = "bcde"

str = "abc"
substr = "bcde"

str = "google"
substr = "ler"

This algorithm will fail if some prefix (but not the complete string) of the substr is also a suffix of str. eg 'le' a prefix of 'ler' is a suffix of 'google'

str = "abcd"
substr = "cdc"

Function falis for above mentioned case. In detail, when first k character(k < substrlen) of substr matches with last k characters of str, this function fails.

Code can be corrected this way

const char* findSubstr(const char* str, const char* substr)
{

    int len = strlen(str);
	int substrlen = strlen(substr);
	int j = 0;
	const char* result = NULL;
	for (int i = 0; i < len; ++i)
	{
		if (str[i] != substr[j])
		{
			j = 0;
			result = NULL;
		}
		else
		{
			if (j==0)
				result = &str[i];

			++j;
			if (j >= substrlen)
				break;
		}
	}
    if(j == substrlen)
	    return result;
    else
        return NULL;
}

Yep, I was pretty surprised this wasn't mentioned earlier.

str="ababcd"
substr="abcd"

It fails because it sets j=0 at first mismatch, but doesn't check if the mismatch is the starting of the substring.

I think the following case will be the problem

original string = "petepeter"
sub string = "peter"

original string = cdcdcdy
sub string = cdcdy

original string = "cdcdcdcdy"
sub string = "cdcdcdy"

const char* findSubstr(const char* str, const char* substr)
{

    int len = strlen(str);
	int substrlen = strlen(substr);
	int j = 0;
	const char* result = NULL;
	for (int i = 0; i < len; )
	{
		if (str[i] != substr[j])
		{
			j = 0;
			result = NULL;
		}
		else
		{
			if (j==0)
				result = &str[i];

			++j;
			++i;
			if (j >= substrlen)
				break;
		}
	}
    if(j == substrlen)
	    return result;
    else
        return NULL;
}

Also the return string is not null terminated properly

str = "google"
substr = "ogl"