做网站效果怎么样,百度指数查询官网入口,ui设计的优势与不足,附近网站建设公司哪家好next数组的作用:当模式串的第j个字符失配时#xff0c;从模式串的第next[j]的继续往后匹配
求模式串的next数组(手算)
next[1]
任何模式串都一样#xff0c;第一个字符不匹配时#xff0c;只能匹配下一个子串#xff0c;因此#xff0c;往后#xff0c;next[1]都无脑写…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] ??????-??????//i1-i2 ababaa- ababaa //j0,第一个字符匹配失败只能匹配下一个子串ij next[1]0; //求next[2] a?????-a?????? //i2 ababaa- ababaa //j1//第一个字符匹配成功第二个字符匹配失败i不动j后退一步 next[2]1; //求next[3] ab????-ab????//i3 ababaa- ababaa//第三个字符匹配失败模式串后退两步j指向1j1 next[3]1 //求next[4] aba???-aba???//i4 ababaa- ababaa//第四个字符匹配失败模式串后退第一个字符a和主串第三个字符a匹配j指向2j2 next[4]2 //求next[5] abab??-abab??//i5 ababaa- ababaa//第五个字符匹配失败模式串后退字符串ab和主串第二个子串ab匹配j指向3j3 next[5]3 //求next[6] ababa?-ababa?//i6 ababaa- ababaa//第六个字符匹配失败模式串后退字符串ab和主串第二个子串aba匹配j指向4j4 next[6]4 例题2同理
