kmp next数组怎样得到

KMP算法中的next数组是通过模式串本身来计算得到的。具体计算方法如下：

1. 首先，next数组的第一个元素next[0]赋值为-1，第二个元素next[1]赋值为0。

2. 接着，从第3个位置开始进行计算。假设当前计算的位置为i，且前一个位置i-1的next值为next[i-1]。

3. 如果模式串的第i个字符和前一个字符不同，那么next[i]的值为前一个字符的next值再加1，即next[i] = next[i-1] + 1。

4. 如果模式串的第i个字符和前一个字符相同，那么就需要进行更复杂的计算。在模式串的前i-1个字符中，找到一个最长的相同的前缀和后缀，其长度为k，那么next[i]的值为k。

5. 如果不存在这样的前缀和后缀，则next[i]的值为0。

6. 通过递推的方式，计算出模式串的所有next值。

需要注意的是，计算next值的过程中，可以使用一个指针j来表示当前相同前缀后缀的长度，同时也可以通过next数组来跳过一些无需比较的位置，从而提高计算效率。