这个挺好记的 但是很容易忘掉
注意‼️‼️ 优先按照下标从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数组