C语言数据结构+KMP算法next数组优化计算方法+优化后子串匹配代码实现

通过我之前那篇KMP算法的讲解,我们可以快速手算KMP算法的next数组,但是之前计算的next数组在一些情况下会有缺陷,比如模式串’aaaab’和主串’aaabaaaab’进行匹配

一.计算根据下列模式串计算出next数组

令模式串指针为j

当第一个元素不匹配时,下一次匹配还是要从模式串的第一个元素与主串匹配,其实我们可以直接写next [1] = 0;,就是当模式串第一个元素就不匹配时next数组对应值直接写0,这样写在我们实现代码时就可以让j = 0时主串和模式串的指针同时往后移动

当第二个元素不匹配时,在匹配失败的元素前面画一条线,然后模式串右移,直到左边没有元素或者左边元素都匹配成功的时候就停下来,从下图可以看到模式串是从第一个元素开始匹配,所以next[1] = 1,这个也可以直接写1,因为在每一个模式串第一个元素不匹配时,next[2]=1

当第三个元素不匹配时,在匹配失败的元素前面画一条线,然后模式串右移,直到左边没有元素或者左边元素都匹配成功的时候就停下来,从下图可以看出next[3]=2

右移,下一次模式匹配的是第二个元素,所以next等于2

当第四个元素不匹配时,在匹配失败的元素前面画一条线,然后模式串右移,直到左边没有元素或者左边元素都匹配成功的时候就停下来,从下图可以看出next[4]=3

当第五个元素不匹配时,在匹配失败的元素前面画一条线,然后模式串右移,直到左边没有元素或者左边元素都匹配成功的时候就停下来,从下图可以看出next[5]=4

综上所述,next数组的为[0,1,2,3,4]

二.优化next数组

通过以上我们会发现,当模式串第二个元素不匹配时,我们默认是将模式串右移一位,让模式串第一个元素与之进行比较,然而这里我们可以看到模式串的第一个和第二个元素是同一个,那么就说第一个元素一定与之不匹配,此时我们就可以直接把next[2]设置为0;
原来匹配失败比较位置

优化后

其他的也是同样的方式

通过以上我们会发现,当模式串第3个元素不匹配时,我们默认是将模式串右移一位,让模式串第2个元素与之进行比较,然而这里我们可以看到模式串的第2个和第3个元素是同一个,那么就说第2个元素一定与之不匹配,此时我们就可以直接把next[2]设置为0;

第四个元素不匹配也是和上面一样让next[4] =0

但是当第五个元素不匹配时,我们只能直到第五个元素一定不是b,但是可能是a,所以我们这里就要模式串的第四个元素与之比较,所以next[5]=4

综上所述,可以得到优化后的next数组等于[0,0,0,0,4]

三.用优化后next的数组代码实现子串的匹配

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
void get_next(char* s, int* next) {int len = strlen(s);next[0] = -1;int k = -1, j = 0;while (j < len - 1) {if (k == -1 || s[j] == s[k]) {++j;++k;if (s[j] != s[k]) {next[j] = k;}else {next[j] = next[k];}}else {k = next[k];}}
}
int kmp(char* s, char* p, int* next) {int slen = strlen(s);int plen = strlen(p);int i = 0, j = 0;while (i < slen && j < plen) {if (j == -1 || s[i] == p[j]) {++i;++j;}else {j = next[j];}}if (j == plen) {return i - j;}else {return -1;}
}
int main() {char s[] = "aaabaaaab";char p[] = "aaaab";int next[5];get_next(p, next);int pos = kmp(s, p, next);if (pos != -1) {printf("子串在主串的%d元素后\\n", pos);}else {printf("匹配失败\\n");}return 0;
}

代码运行:

总结

通过以上的流程图讲解我们可以清楚的了解到优化KMP算法实际就是通过尽可能的减少子串与子串之间的比较次数从而达到高效的子串匹配,最主要我们要先学会next数组的计算再去了解优化后的next数组,这样才会事半功倍,希望本篇文章可以给大家带来帮助!!!