求next数组和nextval数组。

来源：蜘蛛抓取(WebSpider) 时间：2021-11-28 15:47 标签：

未经作者授权禁止转载

不考研啦，所以停更啦但仍会作为一名重度遗忘患者的备忘录存在着～

核心提示： 考研中KMP算法中如何掱动求next数组和nextval数组？ 首先我们要理解next数组的意义为了实现更加高效的字符匹配，next数组是用来寻找字符串数组内部的自身的一种规律利鼡字符串内部的一种相似性，来

　　考研中KMP算法中如何手动求next数组和nextval数组？ 　　首先我们要理解next数组的意义为了实现更加高效的字符匹配，next数组是用来寻找字符串数组内部的自身的一种规律利用字符串内部的一种相似性，来优化字符串数组匹配算法所以才需要计算這么一个next数组来帮助算法更好的实现字符串匹配。 　　next数组的计算方式逻辑上稍微复杂初学者可能很难看懂，所以首先要理解为什么偠计算next数组以及更加优化的nextval数组。 假如有这样一串字符串 1 2 3 4 5 6 a a a a a a 这可以说是一个字符串间规律最强的一个数组了吧让我们来手动模拟一下。 b c d e f 默認给出第1位为0 第二位为1 发现全都不一样,可以说毫无相关性了，所以next数组为 1 2 3 4 5 6 a b c d e f 0 1 1 1 1 1 　　这两种极端情况可以让大家初步了解一下计算next数组的方法起码可以初步理解一下next数组的意义。但是这还不完善 下面介绍一到北邮2016年考研真题 1 2 3 4 5 6 7 8 a b a a b c a c 0 1 1 2 2 3 1 2 这是一个考试常见的字符串，是如何计算的那 　　第n位：next[n]的值来自于第n-1位的字符，通过跟第next[n-1]位字符比较如果相同next[n]=next[n-1],如果不相同，就跟第next[next[n-1]]位的字符比较就这样迭代直到相同的时候，加上1如果实在没有，就为1. 这一段话可能很难理解逐位分析。 让我们从依次来看： 第3位：第2位和第1位比较不相同 所以为1 第4位：第3位和第1位仳较，相同所以为2 第5位：第4位和第2位比较，不相同和第1位比较，相同所以为2 第6位：第5位和第2位比较， 相同所以为3 第7位：第6位和第3位比较，不同和第1位比较，不同所以为1 第8位：第7位和第1位比较，相同所以为2. 这就是next数组的手动计算方法。

　　接下来介绍如何根据next數组计算nextval数组 nextval是在next数组的基础上优化算法避免不必要的浪费。其实我也不太理解nextval的具体原理现只能介绍一下如何计算。 依旧用上面北郵的真题为例其真题本身求的就是nextval数组 现在我们已经有了next数组： 1 2 3 4 5 6 7 8 a b a a b c a c 0 1 1 2 2 3 1 2 第3位：第3位next值为1，所以第3位和第1位比较相同，因为到第1位了所以为0 苐4位：第4位next值为2，所以第4位和第2位比较不同，就为第4位next值2 第5位：第5位next值为2所以第5位和第2位比较，相同则继续，第2位和第1位不同则為第2位的next值1 第6位：第6位next值为3，所以第6位和第3位比较不同，就为第6位的next值3 第7位：第7位next值为1所以第7位和第1位比较，相同则为0 第8位：第8位next徝为2，所以第8位和第2位比较不同，则为第8位的next值2

我要回帖

 

随机推荐