Implement strStr()

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

Solution: first of all, we can think about the brute force method. Starting at the first character of both strings, comparing the content of the two pointers. If the target string ends, we just return the starting point of the first string. If at a time the characters that two pointers pointed are not equal, we proceed to the new start position of the first string. The code is as follows,

C++语言: strStr

01 char *strStr(char *haystack, char *needle) {

02     if(*needle=='\0')

03         return haystack;

04     if(*haystack=='\0')

05         return NULL;

06     //set the start pointer to the beginning of the first string

07     char *start=haystack;

08     char *p;

09     while(*start!='\0')

10     {

11         p=start;

12         //q points to the target string

13         char *q=needle;

14         while(*p!='\0' && *q!='\0' && *p==*q)

15         {

16             p++;

17             q++;

18         }

19         //q ends, return the starting point

20         if(*q=='\0')

21         {

22             return start;

23         }

24         //update the starting position

25         start++;

26     }

27     return NULL;

28 }

However, this method is not quite efficient. If the first string does not contain the second string, the program will loop until the start pointer point to the last character of the first string. But this is not necessary. Why? Assuming that the first string has m characters, and the second string has n characters. We will only need at most m-n+1 times of loops. The reason is that if the first character has less then n remaining characters, and still cannot match the second string, we will know that the first string will not contain the second string. Therefore, we can use an additional pointer (walker), which serves as a counter. Let the walker point to the n-th position of the first string, advancing it through the loop, when it points to '\0', the loop ends. Therefore, we save the time by n steps (The length of the second string). How to make walker advance to n steps further first? Using two pointers! Make another pointer point to the second string, let them walking together. When the second pointer reaches '\0', i.e., after n steps, the first pointer will reach n steps after the beginning of the first string.

C++语言: strStr2

01 char *strStr(char *haystack, char *needle) {
02     if(*needle=='\0')
03         return haystack;
04     if(*haystack=='\0')
05         return NULL;
06     //two pointers, let step point to needle and walker to haystack
07     //advance step to the end of needle, then walker will advance n steps
08     char *step=needle;
09     char *walker=haystack;
10     while(*step!='\0')
11     {
12         step++;
13         walker++;
14     }
15     //back one step
16     walker--;      
17     char *start=haystack;
18     char *p;
19   
20     //using walker to control the loop times
21     while(*walker!='\0')
22     {
23         p=start;
24         char *q=needle;
25         while(*p!='\0' && *q!='\0' && *p==*q)
26         {
27             p++;
28             q++;
29         }
30         if(*q=='\0')
31         {
32             return start;
33         }
34         start++;
35         walker++;
36     }      
37     return NULL;
38 }