```
enter code here
void generateMather(string &pattern,int *matcher)
{
if(!matcher)
return ;
int len=pattern.size();
matcher[0]=0;
matcher[1]=0;
int k=0; //已匹配字符个数
for(int j=2;j<=len;j++)
{
while(k && pattern[k]!=pattern[j-1])
k = matcher[k];
if(pattern[k]==pattern[j-1])
k++;
matcher[j] = k;
}
}
int strStr(string haystack, string needle) {
if(needle.size()==0)
return 0;
if(haystack.size()==0)
return -1;
int *matcher = new int[needle.size()+1];
generateMather(needle,matcher);
int j=0;
for(int i=0;i<haystack.size();i++)
{
while(j && needle[j]!=haystack[i])
j = matcher[j];
if(needle[j]==haystack[i])
j++;
if(needle.size()==j)
{
delete []matcher;
return i-j+1;
}
}
delete []matcher;
return -1;
}
```