当前位置: 代码迷 >> 综合 >> kmp 的 next 数组和 nextval 数据求解
  详细解决方案

kmp 的 next 数组和 nextval 数据求解

热度:53   发布时间:2023-10-19 14:06:50.0

// 本篇仅为学习笔记
// 参考《大话数据结构》

1. next 数组

kmp 的 next 数组和 nextval 数据求解

当 j=1,2 时,其 next 数组的值固定为 0,1
当 j>2 时,比较从模式串(匹配串)T 的第 1 位到 j-1 位的数字相同情况。若有 n 个相同,则 next 的值为 n+1

PS:其中匹配的时候,前后缀不能完全匹配。

2. nextval 数组

nextval 数组建立在已经求得 next 数组的基础上
kmp 的 next 数组和 nextval 数据求解

kmp 的 next 数组和 nextval 数据求解
kmp 的 next 数组和 nextval 数据求解
kmp 的 next 数组和 nextval 数据求解
nextval 的计算方法是,第 n 位的字符如果与它 next 值所指向的(前面的)字符相等(让 next 值和 j 值比较),则继承前面的 nextval 值。否则 nextval = 当前的 next 值。

其中 nextval[1] = 0。