class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.empty()) return 0;
int i, j;
// preprocess
vector<int> b(needle.length() + 1, 1);
i = 0;
j = 1;
b[0] = j;
while(i < needle.length()){
while(j != 1 && needle[i] != needle[j]) j = b[j];
++i, ++j;
b[i] = j;
}
// find
i = 0;
j = 0;
while(i < haystack.length()){
while(j != 1 && haystack[i] != needle[j]) j = b[j];
++i, ++j;
if(j == needle.length()) return i  j;
}
return 1;
}
};
clean kmp


This is the theory of kmp algorithm
http://www.inf.fhflensburg.de/lang/algorithmen/pattern/kmpen.htm