kmp算法模板

void Getnext(string t)
{
  int j = 0, k = -1;
  nex[0] = -1;
  while (j < t.length())
  {
    if (k == -1 || t[j] == t[k])
    {
      j++; k++;
      nex[j] = k;
    }
    else k = nex[k];
  }
}

int kmpmatach(string ms, string ts) {
  int tlen = ts.length();
  for (int i = 0, j = 0; ms[i];) {
    if (j == -1 || ms[i] == ts[j]) {
      if (j == tlen - 1) {
        return i - tlen + 1;  //返回模式串首字符在主串中的位置
      }
      else
        i++, j++;
    }
    else
      j = nex[j];
  }
  return -1;
}