// strstr.cpp - adapted from nkraft by wdg 2009
// Find first occurrence of substring needle in string haystack.
#include <iostream>
using namespace std;

char *strstr ( char *haystack, char *needle );

int main ( ) 
{
   char *one = "concatenate";
   char *two = "cat";
   char *three = "dog";

   char *ans = strstr( one, two );
   if ( !ans )
      cout << "needle1 not found\n";
   else
      cout << "needle1 starts at index " << ans-one 
                                << " of haystack" << endl; 
   ans = strstr( one, three );
   if ( !ans )
      cout << "needle2 not found\n";
   else
      cout << "needle2 starts at index " << ans-one 
                                << " of haystack" << endl; 
  
   return 0;
}

// The function returns pointer to beginning of substring, 
// or NULL if substring is not found.
char *strstr ( char *haystack, char *needle ) 
{
   char *start; 
   for(start = haystack; *start != '\0'; start++ ) {
      char *p = needle;
      char *q = start;
      while ( *p != '\0' && *q != '\0' && *p == *q ) { 
         p++;
         q++;
      }
      if( *p == '\0' ) 
         return start;   // reached end of needle without mismatch
   }  
   return NULL;
}