1已知 字符串 P =“ababaaababaa”,求KMP算法中它的next数组值。(答案格式如:011122310,数字间不加空格) 求法:根据前一个字符的next值求字符串记作 p;next 数组记作 next; 约定: 下标从 1 开始算,注意,不是从 0 开始算 字符串长度 >2 1)第一个字母的 next 值置 0 (next[1] = 0),第二个字母的 next 值置 1(next[2] = 1) ; 2)从第 3 个开始,计算第 i 个位置的 next 值时,检查 p[i-1]== p[next[i-1]] ?(即这两个值是否相等) 解释:第 i 个位置的前一个位置的值(即 p[i-1],记作 m)与以 m 的 next 值(即 next[i-1])为下标的值(即 p[next[i-1]],记作 n)是否相等,(看的懵懵的也没关系,后面会有例子) 若相等,则 next[i] = next[i-1] + 1 若不等,则继续往回找, 检查p[i-1]== p[next[next[i-1]]] ? 若相等,则 next[i] = next[next[i-1]] + 1 若不等,则继续往回找,直到找到下标为 1 还不等(即字符串第一个元素),直接赋值 next[i] = 1