??????/i=1->i=2ababaa-> ababaa //j=0,第一个字符匹配失败,只能匹配下一个子串,++i,++jnext[1]=0;//求next[2]a?????->a??????//i=2。">
当前位置:   article > 正文

数据结构(4.4)——求next数组

数据结构(4.4)——求next数组

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同理:

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/天景科技苑/article/detail/837421
推荐阅读
相关标签
  

闽ICP备14008679号