Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or 

null if needle is not part of haystack.

[解题思路]

时间复杂度线性的解法明显是KMP算法，但是早忘了具体实现了。简单写一个普通的解法。

Update: add a KMP implementation in the end.

[Code]

1:    char *strStr(char *haystack, char *needle) {  2:      // Start typing your C/C++ solution below  3:      // DO NOT write int main() function  4:      if(haystack == NULL || needle == NULL)  5:        return NULL;  6:      int hLen = strlen(haystack);  7:      int nLen = strlen(needle);  8:      if(hLen

[注意]

1. Line 10， 循环的结束应该是hLen-nLen+1，减少不必要运算。

2. Line18， 好久没写指针操作，忘了递增p指针。

增加一个KMP实现, 算法请参考算法导论第３２章。

1:    char *strStr(char *haystack, char *needle) {  2:      // Start typing your C/C++ solution below  3:      // DO NOT write int main() function  4:      if(haystack == NULL || needle == NULL) return NULL;  5:         int hlen = strlen(haystack);  6:      int nlen = strlen(needle);  7:      if(nlen ==0) return haystack;  8:      if(hlen == 0 ) return NULL;  9:      int pattern[100000];  10:      GeneratePattern(needle, nlen, pattern);  11:      return Match(haystack, needle, pattern);  12:    }  13:    void GeneratePattern(char* str, int len, int* pattern)  14:    {  15:      pattern[0] = -1;  16:      int k =-1;  17:      for(int j =1; j< len; j++)  18:      {  19:        while(k >-1 && str[k+1] != str[j])  20:          k = pattern[k];  21:        if(str[k+1] == str[j])  22:          k++;  23:        pattern[j] = k;  24:      }  25:    }  26:    char* Match(char* haystack, char* needle, int* pattern)  27:    {  28:      int hlen = strlen(haystack);  29:      int nlen = strlen(needle);      30:      int k =-1;  31:      for(int j =0; j< hlen; j++, haystack++)  32:      {  33:        while(k >-1 && needle[k+1] != *haystack)  34:          k = pattern[k];  35:        if(needle[k+1] == *haystack)  36:          k++;  37:        if(k == nlen-1)  38:          return haystack-k;  39:      }  40:            return NULL;  41:    }