A3: 实现strStr

strstr是很常用的C库函数，用来在一个字符串中查找一个子字符串是否存在，若存在则返回起点，若不存在则返回NULL。

这题有很多中解法，最直观的方法就是做穷举字符串搜索，复杂度为O(MN)。其中一个小优化技巧就是在外循环中不需要搜索整个字符串，只需循环N-M+1次即可，因为若N-M此之后还未找到匹配，则剩下的长M-1的字符串不需要匹配，因为其长度小于子字符串。

如下：

 

   1: class Solution {

   2:     public:

   3:         char *strStr(char *haystack, char *needle)

   4:         {

   5:             char *p1 = haystack;

   6:             char *p2;

   7:             char *pb;

   8:             char *pp;

   9:  

  10:             if (!*needle)

  11:                 return haystack;

  12:  

  13:             pp = haystack;

  14:             p2 = needle;

  15:             while (*p2++)

  16:                 pp++;

  17:             do {

  18:                 p2 = needle;

  19:                 pb = p1;

  20:                 while (*p2 && *pb && (*p2 == *pb)) {

  21:                     p2++;

  22:                     pb++;

  23:                 }

  24:                 if (!*p2)

  25:                     return p1;

  26:                 pp++;

  27:                 p1++;

  28:             } while (*pp);

  29:             return NULL;

  30:         }

  31: };