kmp中next数组的含义

在KMP算法中，next数组记录了模式串中每个前缀的最长公共前后缀的长度。它表示当模式串中的某个字符与文本串中的某个字符不匹配时，模式串需要向右移动的位数。具体来说，设模式串为p，文本串为t，当前匹配到p[j]和t[i]不匹配，next[j]表示在p[0:j-1]中，存在最长的相等前后缀长度为next[j]，则当p[j]!=t[i]时，p需要向右移动的位数为j-next[j]。计算next数组的过程可以通过动态规划来实现。