kmp算法中的next怎么求

KMP算法中的next数组表示模式串中前缀和后缀的最长公共部分长度。因此，我们需要先从模式串中生成next数组，具体求法如下：

1. 初始化next数组，next[0]=-1，next=0；

2. 设置两个指针i和j，初始时i=2，j=0；

3. 比较p[j]和p[i-1]的值：

① 如果p[j]=p[i-1]，则next[i]=j+1，i++，j++；

② 如果j=0，则next[i]=0，i++；

③ 如果p[j]!=p[i-1]，则将指针j移动到next[j]的位置，循环比较p[j]和p[i-1]的值，直到符合①或②两种情况为止。

4. 重复步骤3，直到i=n。

其中n为模式串的长度。

例如，对于模式串"ABCDABD"，生成的next数组为[-1,0,0,0,0,1,2]。