首先有两步，1求next数组，2进行比对。
我这种是数组后移的方法，即第一个数是-1。
步骤就是如果前后缀不相等，j就要后撤，要后撤因此要有范围。j>=0;
如果相等就j++；
每一次循环求出对应的next[i]。
要注意的点是因为我这是数组后移的方法，因此比较用next[j+1]比较。
2比对跟求next差不多
首先是对目标串进行遍历
不相等就后撤，相等就++；
当j==size()-1时，则匹配成功。
点击查看代码
class Solution {
public:
void getnext(int *next,const string&s){
int j=-1;
next[0]=j;
for(int i=1;i<s.size();i++){
while(j>=0&&s[i]!=s[j+1]){
j=next[j];
}
if(s[i]==s[j+1]){
++j;
}
next[i]=j;
}
}
int strStr(string haystack, string needle) {
int next[needle.size()];
getnext(next,needle);
int j=-1;
for(int i=0;i<haystack.size();i++){
while(j>=0&&haystack[i]!=needle[j+1]){
j=next[j];
}
if(haystack[i]==needle[j+1]){
++j;
}
if(j==needle.size()-1){return i-needle.size()+1;}
}
return -1;
}
};