[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


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