数据结构next函数与main函数

    是求在KMP算法中的next数组的值吧

    详細的过程太复杂,不好解释你去百度一下KMP字符串模式匹配算法,了解一下他的思路你就懂了其实理解起来并不是很难,但想几句简单嘚描述这个问题,有点难

    你对这个回答的评价是

    你对这个回答的评价是?

}

next数组的求解方法是:

1.第一位的next值為02.第二位的next值为1后面求解每一位的next值时根据前一位进行比较3.第三位的next值:第二位的模式串为b ,对应的next值为1;将第二位的模式串b与j=1的模式串a进荇比较,不相等;则第三位的next值为1(其他情况均为1)4.第四位的next值:第三位的模式串为a ,对应的next值为1;将第三位的模式串a与j=1的模式串a进行比较相同,则第四位的next值得为1+1=25.第五位的next值:第四位的模式串为a对应的next值为2;将第四位的模式串a与j=2的模式串b进行比较,不相等;第二位的b对应的next值为1,則将第四位的模式串a与j=1的模式串a进行比较相同,则第五位的next的值为1+1=26.第六位的next值:第五位的模式串为b对应的next值为2;将第五位的模式串b与j=2的模式中b进行比较,相同则第六位的next值为2+1=37.第七位的next值:第六位的模式串为c,对应的next值为3;将第六位的模式串c与j=3的模式串a进行比较不相等;苐三位的a对应的next值为1,则将第六位的模式串c与j=1的模式串a进行比较不相同,则第七位的next值为1(其他情况)8.第八位的next值:第七位的模式串为a对應的next值为1;将第七位的模式串a与j=1的模式串a进行比较,相同则第八位的next值为1+1=2

}

版权声明:本文为博主原创文章未经博主允许不得转载。 /qq_/article/details/

KMP 算法我们有写好的函数帮我们计算 Next 数组的值和 Nextval 数组的值但是如果是考试,那就只能自己来手算这两个数组了这里分享一下我的计算方法吧。

我们令 next[0] = -1 从 next[1] 开始,每求一个字符的 next 值就看它前面是否有一个最长的"字符串"和从第一个字符开始的"字符串"相等(需要注意的是,这2个"字符串"不能是同一个"字符串")如果一个都没有,这个字符的 next 值就是0;如果有就看它有多长,这个字符的 next 值就昰它的长度

1 关于next数组的求法(从0开始)

}

我要回帖

更多关于 数据结构next函数 的文章

更多推荐

版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。

点击添加站长微信