[leetcode]Implement strStr()

Question： Implement strStr().   Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.     Anwser 1：  O(n*m） [cpp]  class Solution {   public:       char *strStr(char *haystack, char *needle) {           // Start typing your C/C++ solution below           // DO NOT write int main() function           int haylen = strlen(haystack);           int needlen = strlen(needle);                      for(int i = 0; i <= haylen - needlen; i++){               char *p = haystack + i;               char *q = needle;               while(*q != '\0'){                   if(*p != *q){                       break;                   } else {                       p++;                       q++;                   }               }                              if(*q == '\0'){                   return haystack + i;               }           }                      return NULL;       }   };       Anwser 2：  O(n + m) KMP [cpp]   class Solution {   public:       char *strStr(char *haystack, char *needle) {           // Start typing your C/C++ solution below           // DO NOT write int main() function           int haylen = strlen(haystack);           int needlen = strlen(needle);           int* fail = new int[needlen];           memset(fail, -1, needlen * sizeof(int));    // strlen(fail)                      int i, j, k;           for (i = 1; i < needlen; ++i) {               for (k = fail[i-1]; k >= 0 && needle[i] != needle[k+1]; k = fail[k]);               if (needle[k+1] == needle[i])                   fail[i] = k + 1;           }                      i = j = 0;                   while(i < haylen && j < needlen)      // while(haystack[i] && needle[j])           {               if (haystack[i] == needle[j])               {                   ++i;                   ++j;               }               else if(j == 0) ++i;               else j = fail[j-1] + 1;           }                      delete fail;                      /*          if (needle[j]) {              return NULL;          }  else {              return haystack + i - j;          }*/           if(j == needlen){               return haystack + i - j;           } else {               return NULL;           }       }   };