kmp算法中的next数组到底怎么算出的?
发布网友
发布时间：2024-12-11 09:13
共1个回答
热心网友
时间：2024-12-11 10:28
KMP算法中，如何手动求next数组和nextval数组？首先我们要理解next数组的意义。next数组是为了实现更高效的字符匹配，利用字符串内部的相似性，优化字符串数组匹配算法。因此，计算next数组是为了帮助算法更好地实现字符串匹配。
next数组的计算逻辑可能看起来较为复杂，初学者可能难以理解。但理解next数组的原因以及nextval数组的优化后，计算方法就变得清晰起来。例如，对于一个简单的数组：
1 2 3 4 5 6
a a a a a a
0 1 2 3 4 5
我们可以手动计算，首先默认第一位是0，第二位是1，从第三位开始求。比较第3位至第1位的字符是否相同，如果相同，则next[3] = next[2] + 1。由此得到的next数组为0 1 2 3 4 5。这种规律性可以帮助优化匹配过程。
接下来，对于一个更复杂的数组：
1 2 3 4 5 6
a b c d e f
0 1 1 1 1 1
在这种情况下，每对字符都不相同，因此next数组为0 1 1 1 1 1。这表明，当字符串中没有相似性时，next数组可以反映出这一点。
让我们通过一个具体的例子来理解计算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位与第1位比较不相同，所以为1；第4位与第1位相同，所以为2；第5位与第2位相同，所以为2；第6位与第2位相同，所以为3；第7位与第1位不相同，与第1位不同，所以为1；第8位与第1位相同，所以为2。这就是next数组的手动计算方法。
接下来，介绍如何根据next数组计算nextval数组。nextval数组是在next数组的基础上进行优化，避免不必要的计算。尽管我也不完全理解其原理，但可以介绍计算方法。对于上述北邮真题为例，计算nextval数组如下：
1 2 3 4 5 6 7 8
a b a a b c a c
0 1 1 2 2 3 1 2
0 1 0 2 1 3 0 2
从第一位置开始，必为0；第二位置与第一位置不同，所以为第一位置的next值1；第三位置与第一位置相同，所以为0；第四位置与第二位置不同，所以为第二位置的next值2；第五位置与第二位置不同，与第一位置不同，所以为第二位置的next值1；第六位置与第三位置不同，所以为第三位置的next值3；第七位置与第一位置相同，所以为0；第八位置与第二位置不同，所以为第二位置的next值2。这就是nextval数组的计算方法。
