【3】5 KMP 手算 next 数组及 nextval 数组

考研中最常考的就是求一个模式串的 next 以及 nextval 数组(手算即可)！

 

串的前缀：包含第一个字符，且不包含最后一个字符的子串。
串的后缀：包含最后一个字符，且不包含第一个字符的子串。

 

当第 j 个字符匹配失败，由前 1~j-1  个字符组成的串记为 S。则：  next[ j ] = S 的最长相等前后缀长度 +1 。  特别的 next[ 1]=0
==>  所以很容易得出 next[1] =0 , next[2] =1 

 

 

 

 

 

 

 

如果不经常出现子串与模式串部分匹配问题，那么 KMP 算法也没屌多少！所以 朴素模式匹配算法现在还在被广泛使用！

 

 

 

 

【nextval 数组】

 有点约分的感觉