class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.empty()) return 0;
if(haystack.empty()) return 1;
vector<int> pi(needle.size(), 0);
//KMPalgorithm:
//Preprocess
int k = 0, i;
for(i = 1; i < needle.size(); i++) {
while(k > 0 && needle[k] != needle[i]) k = pi[k  1];
if(needle[k] == needle[i]) pi[i] = ++k;
}
k = 0;
//Matching
for(i = 0; i < haystack.size(); i++) {
while(k > 0 && haystack[i] != needle[k]) k = pi[k  1];
if(haystack[i] == needle[k]) k++;
if(k == needle.size()) return i  needle.size() + 1;
}
return 1;
}
};
KMP Algorithm using C++


I change " while(k > 0 && needle[k] != needle[i]) k = pi[k  1];" to " while(k > 0 && needle[k] != needle[i]) k =0;" it also acceptted.Is that right ?why?

That is also right, but less efficient. The array "needle" stored the information we've already known. Changing "k = pi[k  1]" to "k = 0", it means you skip the step that search the information we got through previous computation. So, the answer is also right, but the algorithm could cost more time due to repeated computation.

If needle does not have a continuous repeat of the elements ,such as needle="ABCDABCABC" ,there is no different between "k = pi[k  1]" and "k = 0",
I have come up with an example:haystack=AAABAAABAAAE, needle=AAABAAAE；if "k = 0",pi=01201230;if "k = pi[k  1]",pi=01202340.It cost an extra step to find "AAABAAAE" in"AAABAAABAAAE" when we take "k = 0",is that right ?