next数组的作用:当模式串的第j个字符失配时,从模式串的第next[j]的继续往后匹配
求模式串的next数组(手算)
next[1]
任何模式串都一样,第一个字符不匹配时,只能匹配下一个子串,因此,往后,next[1]都无脑写0
next[2]
任何模式串都一样,第二个字符不匹配时,只能匹配模式串的第1个字符,因此,往后,next[1]都无脑写1
next[3]
在不匹配的位置前边,划一条分界线,模式串一步一步往后退,直到分界线之前"能对上",或模式串能完全跨过分界线为止,此时j指向哪儿,next数组值就是多少
next[4]
在不匹配的位置前边,划一条分界线,模式串一步一步往后退,直到分界线之前"能对上",或模式串能完全跨过分界线为止,此时j指向哪儿,next数组值就是多少
next[5]
在不匹配的位置前边,划一条分界线,模式串一步一步往后退,直到分界线之前"能对上",或模式串能完全跨过分界线为止,此时j指向哪儿,next数组值就是多少
next[6]
在不匹配的位置前边,划一条分界线,模式串一步一步往后退,直到分界线之前"能对上",或模式串能完全跨过分界线为止,此时j指向哪儿,next数组值就是多少
总结
next[1]都无脑写0
next[2]都无脑写1
其他next:在不匹配的位置前边,划一条分界线,模式串一步一步往后退,直到分界线之前"能对上",或模式串能完全跨过分界线为止,此时j指向哪儿,next数组值就是多少
例题:
求模式串:ababaa的next数组
//求next[1]
??????->??????//i=1->i=2
ababaa-> ababaa //j=0,第一个字符匹配失败,只能匹配下一个子串,++i,++j
next[1]=0;
//求next[2]
a?????->a?????? //i=2
ababaa-> ababaa //j=1//第一个字符匹配成功,第二个字符匹配失败,i不动,j后退一步
next[2]=1;
//求next[3]
ab????->ab????//i=3
ababaa-> ababaa//第三个字符匹配失败,模式串后退两步,j指向1,j=1
next[3]=1
//求next[4]
aba???->aba???//i=4
ababaa-> ababaa//第四个字符匹配失败,模式串后退,第一个字符a和主串第三个字符a匹配,j指向2,j=2
next[4]=2
//求next[5]
abab??->abab??//i=5
ababaa-> ababaa//第五个字符匹配失败,模式串后退,字符串ab和主串第二个子串ab匹配,j指向3,j=3
next[5]=3
//求next[6]
ababa?->ababa?//i=6
ababaa-> ababaa//第六个字符匹配失败,模式串后退,字符串ab和主串第二个子串aba匹配,j指向4,j=4
next[6]=4
例题2同理: