实现一个字符串 indexOf()的功能。class Solution { public: int next[100005]; int strStr(string haystack, string needle) {
if(needle=="")
return 0;
return KMP(haystack,needle);
}
int KMP(string content,string str)
{
getNext(str);
int i=0,j=0;
while(i<content.length()&&j<str.length())
{
if (j==0 ||content[i]==str[j])
{
if(content[i]==str[j])
j++;
i++;
}
else
{
j=next[j-1];
}
}
if(j>=str.length())
{
return i-str.length();
}
else
return -1;
}
void getNext(string str)
{
next[0]=0;
for(int i=1;i<str.length();i++)
{
int k=next[i-1];
while(k!=0&&str[i]!=str[k])
{
k=next[k-1];
}
if(str[i]==str[k])
next[i]=k+1;
else
next[i]=0;
}
}
};