```
int strStr(string haystack, string needle) {
const int size_h = haystack.size();
const int size_n = needle.size();
if (0 == size_n) return 0;
vector<int> p(size_n, 0);
for (int i = 1; i < size_n; i++) {
int pos = p[i-1];
while (pos > 0 && needle[i] != needle[pos]) pos = p[pos-1];
if (needle[i] == needle[pos]) p[i] = pos + 1;
}
int idn = 0, idh = 0;
for (idh; idh < size_h; idh++){
while (idn > 0 && needle[idn] != haystack[idh]) idn = p[idn-1];
if (needle[idn] == haystack[idh]) idn++;
if (idn == size_n) return idh - size_n + 1;
}
return -1;
}
```