这个挺好记的 但是很容易忘掉

注意‼️‼️ 优先按照下标从0开始

注意‼️‼️ 优先按照下标从0开始

注意‼️‼️ 优先按照下标从0开始

下标从1开始有坑 手算下标为1开始的nextval数组时 有时候next数组对应为0 但是模式串下标1开始没有0 这种0要和正常算出的0区分开来 可以标记为负1 匹配失败遇到j等于nextval[j]=负1时 就i加加j加加 甚至从下标为1开始和从0开始算的结果都不一样滑动距离也不一样

若串元素序号从0开始,则next[0]=-1

若串元素序号从1开始,则next[1]=0

模式串的字符序号可能从0开始也可能从1开始,从0开始得到的next数组所有元素+1就得到了序号从1开始的next数组,目前来看408中串序号默认是从0开始。

注意❗️这三个串是对模式串求出的 不是主串

先求出pm数组 这个一定要注意很容易算错 前缀和后缀公共部分的最长长度 一定要看仔细前后缀都有什么 “a”的最长公共前后缀长度为0

注意‼️最长公共前后缀长度时不要包含整个串 例如“aaa” 最长为2 不是3 因为3是整个串了

再pm数组整体右移一位 第一位根据上边的规则补0或者1 就得到了next数组

下标从0开始:匹配时 一旦j变成了-1!这时要同时做两件事:i += 1;j +=1!(下标从1开始则是j变成0时执行i++ j++)

例如 2024年第六题

主串 a a b a c a b

模式串 a a b a a b

模式串 a a b a a b

下标为4的位置 主串的c和模式串的a匹配失败此时nextval[4]等于-1 模式串要右移5位 模式串的第一位要在主串的c后那一位 所以滑动距离为5

nextval数组

第一位默认和next规则一样 下标为0开始默认值为负1 下标为1开始默认值为0

所以从第二位开始比较

将A[next[j]]写出来看看是否与A[j]相等

若不相等 则nextval[j]等于next[j]

否则 nextval[j]等于nextval[next[j]]

由此得到nextval数组

最后修改:2026 年 07 月 21 日