本文主要是介绍计软: KMP算法的next函数怎么计算，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
计软刷题时刷到一个题目，模式串p为“abaac”，求其next函数。代码就不解析了（我也没咋看），为了应试总结了一个快速答题技巧。参考数据结构——关于KMP算法中next函数的详细解析_初来乍到-CSDN博客_数据结构next函数
首先，按位序、模式串、next函数写下来：
| 位序 | 1 | 2 | 3 | 4 | 5 |
| 模式串 | a | b | a | a | c |
| next值 |
第一步：next值的前两位是0和1，代码是这样初始化的，记住就行了
| 位序 | 1 | 2 | 3 | 4 | 5 |
| 模式串 | a | b | a | a | c |
| next值 | 0 | 1 |
第二步：计算next第3位，即next[3]的值
| 位序 | 1 | 2 | 3 | 4 | 5 |
| 模式串 | a | b | a | a | c |
| next值 | 0 | 1 | 当前计算结果=1 |
比较基准：用前一位的模式串进行比较，记作模式串[2]吧，模式串[2] = b, 即比较基准为‘b’。
比较对象：与什么比较呢，前一位next值所对应的位序上的字符进行比较，因为next[2] = 1，所以与位序1上的字符即模式串[1] = a比较。将b与a进行比较。
计算结果：如果不相等，结果为1；如果相等，在前一位next值上+1。比较到模式串第一个字符为止。这里已经比较到第一个模式串字符了，而且b！=a，所以结果为1.
第三步：计算next第4位，即next[4]的值
| 位序 | 1 | 2 | 3 | 4 | 5 |
| 模式串 | a | b | a | a | c |
| next值 | 0 | 1 | 1 | 当前计算结果=2 |
比较基准：用前一位的模式串进行比较，即模式串[3] = a, 即比较基准为‘a’。
比较对象：与什么比较呢，前一位next值所对应的位序上的字符进行比较，即与next[3] = 1位序上的字符比较，即模式串[1] = a。将a与a进行比较。
计算结果：如果不相等，结果为1；如果相等，在前一位next值+1。比较到模式串第一个字符为止。这里已经比较到第一个模式串字符了，而且a=a，所以结果为next[3]+1 = 1+1 = 2.
第四步：计算next第5位，即next[5]的值
| 位序 | 1 | 2 | 3 | 4 | 5 |
| 模式串 | a | b | a | a | c |
| next值 | 0 | 1 | 1 | 2 | 当前计算结果=2 |
比较基准：用前一位的模式串进行比较，即模式串[4] = a, 即比较基准为‘a’。
比较对象：
与前一位next值所对应的位序上的字符进行比较，即与next[4] = 2位序上的字符比较，即模式串[2] = b。将a与b进行比较，不相等，当前结果初始化为1。
因为没有比较到第1位的字符串，接着比较：与位序为next[2] = 1的字符比较，即模式串[1]=a。将a与a比较，相等，当前结果+1，即结果为1+1 = 2. 因为已经比较到第一位字符串了，所以比较结束。
最终，next值为01122.
总结一下，就是next的最开始两位为01.接下来每一位的值，都是用前面的一位模式串值去比较，一直比较到模式串的第一位为止。如果相等，当前结果为前一位的next值+1，如果不等，则初始化为1.
这篇关于计软: KMP算法的next函数怎么计算的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
