int strStr(string haystack, string needle) {
if (needle.length() == 0){
return 0;
}
int next[needle.length()];
getNext(needle,next);
int i = 0,j = 0;
while( i < (int)haystack.length() && j < (int)needle.length()&&(i - j) <(int)(haystack.length()-needle.length())+1 ){
if ( j == -1 ||haystack[i] == needle[j]){
j++;
i++;
} else{
j = next[j];
}
}
if (j == needle.length()){
return i-needle.length();
} else{
return -1;
}
}
void getNext(string needle,int next[]){
int j = 0;
int k = -1;
next[0]=-1;
while (j< needle.length()){
if (k == -1 || needle[j] == needle[k]){
++j;
++k;
next[j]=k;
// if (needle[j] != needle[k]){
// next[j] = k;
// } else{
// next[j] = next[k];
// }
} else{
k = next[k];
}
}
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
