1 vector<int> getNextList(string needle)
 2 {
 3     vector<int> next(needle.size());
 4     int j = 0;
 5     next[0]=0;
 6 
 7     for (int i = 1; i < needle.size(); i++)
 8     {
 9         while (j > 0 && needle[j] != needle[i])
10         {
11             j = next[j - 1];
12         }
13 
14         if (needle[i] == needle[j])
15         {
16             j++;
17         }
18 
19         next[i] = j;
20     }
21 
22     return next;
23 }
24 
25 
26 int strStr(string haystack, string needle) 
27 {
28     if (needle.size() == 0) {
29         return 0;
30     }
31 
32     auto next = getNextList(needle);
33 
34     int i = 0;
35     for (int j = 0; j < haystack.size(); j++)
36     {
37         while (i > 0 && needle[i] != haystack[j])
38         {
39 
40             i = next[i - 1];
41             cout << i;
42 
43         }
44 
45         if (haystack[j] == needle[i])
46         {
47             i++;
48         }
49 
50         if (i == needle.size())
51             return j - needle.size() + 1;
52     }
53 
54     return -1;
55 }