目录
一、手动计算next数组
二、使用next数组进行模式匹配
三、练习
一、手动计算next数组
next[2] 表示模式串和主串对比,模式串里面第2个字符和主串不匹配,j应该指向几?
首先:字符串的下标和next数组下标保持一致
字符串是1~6,next数组也是1~6
以后next[1]=0和next[2]=1是固定的,无脑写就行
在不匹配的位置前面画一条分界线,模式串一步步后退,直到分界线前面字符都能“对得上”,匹配了,或者模式串完全跨国分界线,
⬇
⬇
⬇
⬇
此时j指向哪里,next数组就是几 ,所以next[3]=1
当第4个字符匹配失败
⬇
⬇
当第5个匹配失败,在第5个前面画一条分隔线
⬇
⬇
⬇
⬇
⬇
⬇
发现匹配了, j 数组指向2,所以next[5]=2
按照步骤一步一步推理,依次求出next数组,如下图
二、使用next数组进行模式匹配
⬇
⬇
如图j=1,开始接着模式串和主串匹配,
发现匹配失败让j=next[j] ,图中j=1,看next数组,next[1]=0,所以模式串右移动,如下图
三、手算练习
计算next[3]=??
画分割线在第3 个位置前面如下图
⬇
⬇
计算next[4]=??
⬇
⬇
⬇
⬇
匹配了所以next[4]=2
依次步骤算出next数组如下图
三、练习
答案:
01234