## Saturday, December 22, 2012

### [LeetCode] Implement strStr() 解题报告

Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
» Solve this problem

[解题思路]

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<nLen)
9:        return NULL;
10:      for(int i=0; i<hLen - nLen+1; i++)
11:      {
12:        int j=0;
13:        char* p = &haystack[i];
14:        for(; j< nLen; j++)
15:        {
16:          if(*p != needle[j])
17:            break;
18:          p++;
19:        }
20:        if(j == nLen)
21:          return &haystack[i];
22:      }
23:      return NULL;
24:    }
``````

[注意]
1. Line 10， 循环的结束应该是hLen-nLen+1，减少不必要运算。
2. Line18， 好久没写指针操作，忘了递增p指针。

``````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:    }
``````