Substring search interview question

Question

char* func( char* a, const char* b )
{
    while( *a )
    {
        char *s = a, *t = b;
        while( (*s++ == *t++) && *s && *t );

        if( *t == 0 )
            return a;
        a++;
    }
    return 0;       
}

The above code was written to search for the first instance of string "b" inside of string "a."

Is there any problem with the above program?

Is there any approach to improve the efficiency of it?

Answer 1

I'm not a C developer so I can't nor will comment on the correctness of the code but with regards to efficiency, see:

http://en.wikipedia.org/wiki/String_searching_algorithm

I believe you have the naive searching version. Look at the Knuth-Morris-Pratt algorithm. You can do a little work on the string b before you are searching in a. And then you can do it in O(|a|+|b|). And |b| is larger than |a| then b can't be in a so it becomes O(|a|).

The essence is that if a is:

abcabe

And b is:

aba

Then you know that if the third char fails then a search will also fail if you shift b one char or two chars. Therefore you don't have to check every possible substring:

a[1 .. 3] == b
a[2 .. 4] == b
...

which is O(|a|*|b|) chars but only a subset which is equal to O(|a|)

Answer 2

• If a is not properly null-terminated, the function will die horribly.
• If b is not properly null-terminated, the function will probably die horribly.
• The indentation is strange.

Answer 3

This is going to do the job but I there are better ways to do this. Check this article: http://en.wikipedia.org/wiki/String_searching_algorithm

Answer 4

yeah...

• t can't be assigned b as its destroying const.
• it doesn't match the last char in "b" properly.

Answer 5

If a points to "cat" and b points to "ab", func will return a pointer to "at" (the wrong value) instead of 0 (the intended value) because the pointer t is incremented even though the comparison (*s++ == *t++) fails.

For completeness' sake and in order to answer the second question, I'd offer one solution (surely among other viable ones): Have the result of the comparison be assigned to another variable, e.g. while( ( flag = ( *s++ == *t++ ) ) && *s && *t ); and then if( flag && *t == 0 ).

Answer 6

Very picky point, in addition to those raised by others:

If a and b are both 0-length, then this routine returns NULL. If it's supposed to be following the specification of strstr, then it must return a in that case. Which makes sense, since the empty string b is indeed a substring of the empty string a.

Answer 7

I think the line:

while( (*s++ == *t++) && *s && *t );

is undefined because you are accessing the variables after the post-increment they might be before the increment or after the increment.

Unless they changed it, side effects of expressions are undefined by the standard as to when they take effect. The only thing guaranteed is *s++ will access s first and then increment for the next statement. What is undefined is whether the && s and && t see the value before or after the increment...

Answer 8

Well, it does have the slight problem that it doesn't actually work.

Try running with a="xyz" and b="xw". When you hit the while loop the first time, x=x, you increment both pointers, and loop around again. Then y!=w, so you exit the loop. But you've already incremented the pointers, so t==0, and you report a hit.

In general, you report a hit regardless of whether the last character matches.

If b is a 1-character string, the last character is the only character, so a 1-character string matches anything.

I'd recommend against trying to do the loop with a single statement with side effects. As this example illustrates, this is tricky. Even if you get it right, it's very cryptic for people trying to read your code.

Answer 9

Why do you not use a function for your work? Do you know strstr()?

const char* mystrstr(const char* a,const char* b)
{
  size_t blen=strlen(b);
  while( *a )
  {
    if( !strncmp(a,b,blen) )
      return a;
    ++a;
  }
  return 0;       
}

Answer 10

*t = b; //killing the const-ness of b....

Also to clarity to code you can do while(*a!= '\0') instead of while(*a) Also the second while statement : while( (*s++ == *t++) && *s && *t ); will fail....Try to take int flag = (*s++ = *t++) ; and do bit of simplification