void GetNextval(string partStr, vector<int>& nextval)
{
int p_len = partStr.size();
//由 next[i] = j 得，也就是对于位置 i 来说，
//区段[0, i - 1] 的最长相同真前后缀分别是[0, j - 1] 和[i - j, i - 1]，即这两区段内容相同。
int i = 0; // P 的下标
int j = -1;
nextval[0] = -1;
while (i < p_len)
{
// j == -1 存在的意义是何？
// 第一，程序刚运行时，j 是被初始为 -1，直接进行 P[i] == P[j] 判断无疑会边界溢出；
// 第二，else 语句中 j = next[j]，j 是不断后退的，若 j 在后退中被赋值为 -1（也就是 j = next[0]），在 P[i] == P[j] 判断也会边界溢出。
// 综上两点，其意义就是为了特殊边界判断。
if (j == -1 || partStr[i] == partStr[j])
{
i++;
j++;
nextval[i] = j;
//为了防止出现ABCDAB 若在 i = 5 时匹配失败，此时应该把 i = 1 处的字符拿过来继续比较，
//但是这两个位置的字符是一样的，都是 B，既然一样，拿过来比较不就是无用功了么？
//所以将nextval[i] = j;优化，如果相同就继续往前找前缀
if (partStr[i] != partStr[j])
nextval[i] = j;
else
nextval[i] = nextval[j]; // 既然相同就继续往前找真前缀
}
else
j = nextval[j];
}
}
int KMP(string mianStr, string partStr) {
int partLen = partStr.length();
vector<int> nextList(partLen+1,0);
GetNextval(partStr, nextList);
int i = 0;
int j = 0;
while (i < mianStr.length()&& j < partLen)
{
if (j==-1|| mianStr[i] == partStr[j])
{
i++;
j++;
}
else
{
j = nextList[j];
}
}
if (j == partLen)
{
return i - j;
}
return -1;
}
