[Leetcode] Implement strStr()

 1 class Solution {
 2 public:
 3     void getNext(char *patten, int next[]) {
 4         int i = 0, j = -1;
 5         next[i] = j;
 6         while (patten[i] != ‘\0‘) {
 7             while (j >= 0 && patten[i] != patten[j]) 
 8                 j = next[j];
 9             ++i; ++j;
10             next[i] = j;
11         }
12     }
13     
14     char *strStr(char *haystack, char *needle) {
15         if (haystack == NULL || needle == NULL) 
16             return NULL;
17         if (needle[0] == ‘\0‘) 
18             return haystack;
19             
20         int i = 0, j = 0;
21         char *pos = NULL;
22         int *next = new int[strlen(needle) + 1];
23         getNext(needle, next);
24         while (haystack[i] != ‘\0‘) {
25             while (j >= 0 && haystack[i] != needle[j])
26                 j = next[j];
27             ++i; ++j;
28             if (needle[j] == ‘\0‘) {
29                 pos = haystack + i - j;
30                 return pos;
31             }
32         }
33         return pos;
34     }
35 };

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 void getNext(const char *patten, int next[]) {
 6     int i = 0, j = -1;
 7     next[i] = j;
 8     while (patten[i] != ‘\0‘) {
 9         while (j >= 0 && patten[j] != patten[i]) 
10             j = next[j];
11         ++i; ++j;
12         next[i] = j;
13     }
14 }
15 
16 int kmpSearch(const char *s, const char *p, const int next[]) {
17     int i = 0, j = 0;
18     int pos = -1;
19     while (s[i] != ‘\0‘) {
20         while (j >= 0 && s[i] != p[j])
21             j = next[j];
22         ++i; ++j;
23         if (p[j] == ‘\0‘) {
24             pos = i - j;
25             cout << s[i-j]<< endl;;
26             return pos;
27         }
28     }
29     return pos;
30 }
31 
32 int main() {
33     char p[1024], s[1024];
34     int *next;
35     cin >> s >> p;
36     next = new int[strlen(p)+1];
37     getNext(p, next);
38     cout << kmpSearch(s, p, next) << endl;
39     return 0;
40 }