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[解题思路]
时间复杂度线性的解法明显是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<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指针。
增加一个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: }