所有栏目 | 戒烟百科网
你的位置:首页 > 香烟知识 » 正文

kmp算法的下一步是什么?

发布时间:2020-03-21

作品分类:kmp  next  算法  模式  值为  第三位
kmp算法中的next到底是什么意思啊?

  先看看next数据值的求解方法  位序 1 2 3 4 5 6 7 8  模式串 a b a a b c a c  next值 0 1 1 2  2 3  1 2  next数组的求解方法是:  1.第一位的next值为0  2.第二位的next值为1  后面求解每一位的next值时,根据前一位进行比较  3.第三位的next值:第二位的模式串为b ,对应的next值为1;将第二位的模式串b与第一位的模式串a进行比较,不相等;则第三位的next值为1  4.第四位的next值:第三位的模式串为a ,对应的next值为1;将第三位的模式串a与第一位的模式串a进行比较,相同,则第四位的next值得为2  5.第五位的next值:第四位的模式串为a,对应的next值为2;将第四位的模式串a与第二位的模式串b进行比较,不相等;第二位的b对应的next值为1,则将第四位的模式串a与第一位的模式串a进行比较,相同,则第五位的next的值为2  6.第六位的next值:第五位的模式串为b,对应的next值为2;将第五位的模式串b与第二位的模式中b进行比较,相同,则第六位的next值为3  7.第七位的next值:第六位的模式串为c,对应的next值为3;将第六位的模式串c与第三位的模式串a进行比较,不相等;第三位的a对应的next值为1,则将第六位的模式串c与第一位的模式串a进行比较,不相同,则第七位的next值为1  8.第八位的next值:第七位的模式串为a,对应的next值为1;将第七位的模式串a与第一位的模式串a进行比较,相同,则第八位的next值为2  以上这种分析方法,位序是从1开始的,如果位序从0开始,刚第一位的next值为-1,后面的方法则相同

留言与评论(共有 0 条评论)
   
验证码:
Top