KMP solution offered by fff

class Solution {
public:
vector<int> getNext(string needle) {
if (needle.size() == 0) return vector<int>();
vector<int> next(needle.size()+1);
int i = 0;
int j = -1;
next[i] = j;
while (i < needle.size()) {
while (j != -1&& needle[i]!=needle[j]) j = next[j];
next[++i] = ++j;
}
return next;
}
int strStr(string haystack, string needle) {
if (needle == "") return 0;
if (haystack == "") return -1;
if (needle.size() > haystack.size()) return -1;
vector<int> next = getNext(needle);
int i = 0;
int j = 0;
while (i < haystack.size()) {
while (j != -1 && haystack[i] != needle[j]) j = next[j];
i ++;
j ++;
if (j == needle.size()) {
return i - j;
}
}
return -1;
}
};