KMP算法

next[j]前面的字符和j前面的字符是相同的。
当不匹配时，i不移动，j向前指向next[j]。此时再对s1[i]和s2[j]进行比较即可，前面的已经匹配了。

int kmp(string s, string p, vector<int> next){
  int slen=s.length(), plen=p.length();
  int i=0,j=0;
  while(i<slen && j<plen){
    if(j==-1 || s[i]==p[j]){ //模式串的第一个元素就不匹配||匹配时
      i++;
      j++;
    }
    else
      j=next[j];
  }
  if(j==plen)
    return i-plen;
  else
    return -1;
}

求next[]:

vector<int> getNext(string p){
  int len=p.length();
  vector<int> next(len,0);
  next[0]=-1;//第一个元素就不匹配，j不能往前跳了，将其设为-1，作为一个标记
  int i=0,j=next[i]; 

  while(i<len-1){ //求next[i+1]
    if(j==-1 || p[i]==p[j]){
      next[i+1]=j+1;
      i++;
      j++;
    }
    else
      j=next[j];
  }
  return next;
}