KMP字符串匹配算法求next及nextval数组的方法_kmp算法nextval怎么出来的

前言

字符串匹配算法多种多样，这里先对数据结构中经典的字符串匹配算法进行介绍
再讲解本文重点：如何求KMP算法中的next及nextval数组值

1.朴素的模式匹配算法
朴素的模式匹配算法也称为布鲁特-福斯（BF）算法，其基本思想是：从主串的第一个字符起与模式串的第一个字符比较，若相等，则继续逐个字符进行后续的比较;否则从主串的第二个字符起与模式串的第一个字符重新比较，直至模式串中的每个字符依次和主串中的一个连续的字符序列相等，则称匹配成功。如果不能在串中找到与模式串相同的子串，则匹配失败。
2.改进的模式匹配算法
改进的模式匹配算法又称为KMP算法，其改进之处在于：每当匹配过程中出现相比较的字符不相等时，不需要回溯主串的指针，而是利用已经得到的“部分匹配”的结果，将模式串向后“滑动”尽可能远的距离，再继续进行比较。

求next数组的方法详述

1. 求模串abaababb的next数组，设置表如下
   

2. 分别设置next[1]和next[2]的值为0和1
   

3. 要求i位置next值时，观察前一个位置，即i-1位置
   (1). 设置一个固定指针指向i-1位置，一个移动指针j首先指向i-1
   (2). 如果i-1位置的字符和j位置next指向的字符相同，则设置next为j位置next值+1
   (3). 如果不相同则让j指针移动到目前next指向的位置。直到i-1位置的字符和j位置next指向的字符相同或者j位置next指向0，则设置next为j位置next值+1

   如:这里求序号3的next值，则观察序号2的next值,发现其next值指向序号1。
   而序号1对应的字符a与序号2对应的字符不相同，故j继续移动，但此时发现
   序号1的next为0，已经不能再往前了。故next取此时j指向的next+1。即0+1=1
   1
   2
   3

4. 以下是相同时的情况
   
   
   

求nextval数组的方法详解

大家来看一个例子:
主串s=“aaaaabaaaaac”
子串t=“aaaaac”
这个例子中当‘b’与‘c’不匹配时应该‘b’与’c’前一位的‘a’比,这显然是不匹配的。
'c’前的’a’回溯后的字符依然是‘a’。
我们知道没有必要再将‘b’与‘a’比对了，因为回溯后的字符和原字符是相同的，原字符不匹配，回溯后的字符自然不可能匹配。但是KMP算法中依然会将‘b’与回溯到的‘a’进行比对。这就是我们可以改进的地方了。我们改进后的next数组命名为：nextval数组。KMP算法的改进可以简述为： 如果a位字符与它next值指向的b位字符相等，则该a位的nextval就指向b位的nextval值，如果不等，则该a位的nextval值就是它自己a位的next值。 这应该是最浅显的解释了。如字符串"ababaaab"的next数组以及nextval数组分别为：

本文多数内容据转载而来，在原博客的博主提供了一个她自己写的html5测试网站，我也将其放在这里方便测试时使用：next及nextval数组测试链接
（试了几组数据，这个网站应该是没问题的）

附转载的原文链接