strstr implementation

Question

Please review my strstr implementation. This is an interview question that does not allow the use of strlen(). Is there a better way than using a boolean below?

#include <iostream>
#include <cstring>
char* my_strstr(char * s1, const char *s2)
{
  if ( s1 == NULL || s2 == NULL )
    return NULL;

  size_t s2Size = 0;

  const char *end = s2;
  while (*end++)
    ++s2Size;

  bool match;
  while ( *s1 )
  {
    match = true;
    for ( int i = 0; i < s2Size ; ++i )
    {
      if ( s1[i] != s2[i] )  
      {
        match = false;
        break;
      }
    }
    if ( match )
      return s1;

    ++s1;
  }
  return NULL;
}

const char* my_strstr(const char * s1, const char *s2)
{
  return my_strstr(const_cast<char*>(s1),s2);
}


int main()
{
  const char str[]= "This is a strstr test";
  const char search[]= "strstr";

  const char *result = my_strstr(str,search);

  if ( result )
    printf("original: %s\n item: %s\n found: %s\n", str, search, result );
}

Answer 1

By counting the length of s2, you missed the point of this exercise. Technically, you didn't call strlen(), but you emulated it, which is arguably even worse. The point was to test your proficiency with pointers, and you failed this interview question. (Why not count the length? Because it's possible to do it without incurring the cost of that O(n) operation. The only time you need to walk along the entire length of s2 is when a match is imminent.)

The strstr(3) documentation probably calls the arguments s1 and s2. However, I'll borrow a rare piece of wisdom from the PHP documentation and call the arguments haystack and needle.

Don't use variables to control the execution flow. Prefer to use more active means such as continue, break, and return. If you have detected a match, what are you waiting for? Celebrate your success with an immediate return!

Your imports are wrong. The only library function you call is printf(), so you should #include <cstdio>.

Here's a solution.

#include <cstdio>

char* my_strstr(char *haystack, const char *needle) {
    if (haystack == NULL || needle == NULL) {
        return NULL;
    }

    for ( ; *haystack; haystack++) {
        // Is the needle at this point in the haystack?
        const char *h, *n;
        for (h = haystack, n = needle; *h && *n && (*h == *n); ++h, ++n) {
            // Match is progressing
        }
        if (*n == '\0') {
            // Found match!
            return haystack;
        }
        // Didn't match here.  Try again further along haystack.
    }
    return NULL;
}

const char* my_strstr(const char *haystack, const char *needle) {
    return my_strstr(const_cast<char *>(haystack), needle);
}

int main() {
    const char *str = "This is a strstr test";
    const char *search = "strstr";

    const char *result = my_strstr(str, search);

    if (result)
        printf("original: %s\n item: %s\n found: %s\n", str, search, result);
    return 0;
}

Answer 2

I think interviewers like this task to see how you might be able to code/design on your feet. How readable is your implementation? Did you use four variables and three loops when fewer are sufficient? Do you think in pointers or arrays? Do you really know C, or do you think in some other language and translate it internally into C? Is your code pedantic, obtuse, obfuscated, sick or slick? Did you pay attention to the edge cases?

char * strstr(const char *haystack, const char *needle) {  
    const char *a = haystack, *b = needle;  
    for (;;)  
        if      (!*b)          return (char *)str;  
        else if (!*a)          return NULL;  
        else if (*a++ != *b++) { a = ++haystack; b = needle;}  
}

If the interviewer is willing to take a bet, then bet that you can write strstr without using any local variables or calling any other external routines. If they take the bet, then try to up the bet by saying you can write it without using any for or while or gotos. Produce the recursive version below. Agree that it is not efficient.

char * strstr(const char *haystack, const char *needle) {
    if (!*needle)
        return (char *)haystack;
    if (!*haystack) 
        return NULL;
    if ((*haystack == *needle) && (strstr(haystack+1, needle+1) == haystack+1)) 
        return (char *)haystack;
    return strstr(haystack+1, needle);
}

Answer 3

Yep.

You implemented the standard brute force implementation.

Personally I think that is fine. For some silly reason though a lot of interviewers expect you to swat up on string manipulation for interviews and want you to know the non brute force versions off the top of your head. In my opinion if you know a clever versions exists is enough (because in real life I would Google "efficient strstr implementation") if you happen to know the name even better (because in real life you will find it faster).