[LeetCode] 28. Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

 1 int* preprocess(char *needle)
 2 {
 3     int len = strlen(needle);
 4     int *p = (int *)malloc(sizeof(int) * len);
 5     int j = -1;
 6     
 7     for (int i = 0; i < len; i++){
 8         p[i] = -1;
 9     }
10 
11     for (int i = 1; i < len; i++){
12         while ((j >= 0) && (needle[j+1] != needle[i])) j = p[j];
13         if (needle[j + 1] == needle[i]) j++;
14         p[i] = j;
15     }
16 
17     return p;
18 }
19 
20 int strStr(char* haystack, char* needle) {
21     char *ph = haystack;
22     char* pn = needle;
23     char* pstart = NULL;
24   
25     if (!*needle) return 0;
26     if (!*haystack) return -1;   
27 
28     int* p = preprocess(needle);
29     
30     int j = -1;
31     for (int i = 0; i < strlen(haystack); i++){
32         while ((j >= 0) && (needle[j+1] != haystack[i])) j = p[j];
33         if (needle[j + 1] == haystack[i]) j++;
34         if ((j + 1) == strlen(needle))
35            return (i - strlen(needle) + 1); 
36     }
37 
38     return -1;
39 }