KMP算法(Knuth-Morris-Pratt) 是一个字符串的匹配算法,其中有一部分算法需要求解next数组来求解该位置前面字符串的最长相同的真前缀和真后缀长度。
next数组的求解方法为:第一位的next值为0,第二位的next值为1,后面求解每一位的next值时,根据前一位进行比较。首先将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值加上1;如果不等,向前继续寻找next值对应的内容来与前一位进行比较,直到找到某个位上内容的next值对应的内容与前一位相等为止,则这个位对应的值加上1即为需求的next值;如果找到第一位都没有找到与前一位相等的内容,那么需求的位上的next值即为1。
还是有点难看懂,举个例子:求解模式串 "ababaaabbaa "的next数组,首先先画一个表格便于观察其中的奥秘。在这之前我们要知道模式串中前两个位的next值分别为0,1。
先为模式串构建这样一张表,其中第一位和第二位的next值先填入0和1,接下来计算第三位(即下标为3的数据'a')的next值。
第三位:首先看第三位的前一位即第二位的值(在上面的例子中,这个值为'b'),然后再看第二位的next值,该next值作为下标值找到对应的元素,比较第二位的值是否和这个下标对应的值相等,可以看出第二位的next值对应的值是'a',显然a不等于b,而a的next值已经没有对应的下标元素了,即已经没有下标为0的元素了,因此第三位的next值为1(如果找到最前面也没有找到相等的元素那么所求的next值就为1)。
第四位:和第三位的求解方法一样,先看第四位的前一位即第三位的值为a,再将第三位的next值作为下标值对应到表中找出对应的元素,比较该元素是否与第四位的前一位的元素相同,如果相同那么第四位的next值就是前一位的next+1。显然第三位的next值作为下标对应的值也为a,两者相等,因此第四位的next值为第三位的next值+1=2。
第五位:和之前的方法一样,将第四位的next值作为下标值找对应的值来与第四位的值(a)相比是否相等,正好,第四位next值对应的下标的元素也是b,所以第五位的next值为第四位的next值+1=3。
第六位:相同的方法,将第五位的next值作为下标找到对应的元素,比较是否与第五位的值相等,很凑巧,也相等,所以第六位的next值为第五位的next值+1=4。
第七位:将第六位的next值(4)作为下标值找到对应的值,这次发现第六位的值是'a',但是下标为4对应的值是'b',两者不相等,所以再将下标为4的next值(2)再作为下标值找对应的值,再比较是否和第六位的值相等,显然下标为2的值还是'b',与第六位的'a'不相等,因此再将下标为二的next值再作为下标值比较对应的值是否与第六位的值相等,这次发现下标为1的值和第六位相等了,所以第七位的next值就等于第二位的next值+1=2,因为最后是从第二位的next值找到第一位的。也可以看作是第七位的next值等于第一位的 下标值+1。
第八位:将第七位的next值作为下标找到对应的值2,与第七位的值'a'做比较,发现不相等,于是将第二位的next值作为下标找到对应值,两者相等都为a,所以第八位的next值=第二位的next值+1=2。
第九位:将第八位的next值作为下标值找到对应的值,比较是否与第八位的值相等,这次发现相等了,因为第八位的next值(2)作为下标对应的值也是b,因此第九位的next值=第八位的next值+1=3。
第十位:将第九位的next值作为下标找到对应的值,再比较,发现两者都为a,因此第九位的next值=第八位的next值+1=4。
第十一位:将第十位的next值作为下标找到对应的值进行比较,发现两者相等,因此第十一位的next=第十位的next+1=5。
第十二位: 将第十一位的next值作为下标找到对应的值进行比较,发现两者相等,因此第十二位的next=第十一位的next+1=6。
文章来源:https://www.toymoban.com/news/detail-498967.html
所以该字符串的next数组为:011234223456文章来源地址https://www.toymoban.com/news/detail-498967.html
到了这里,关于KMP算法中的next数组求解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!