高效"KMP"字符匹配算法就这么简单
1、聊一聊
上一篇文章
2、KMP算法介绍
1
2
3、原理分析
1
按照之前的做法，如果已经匹配过的aaaa中前两个字节等于后两个字节，那么模式串应该移动两个字节，然而我们发现其只需要移动一个字节就能匹配成功了，看来仅仅用之前的策略还不够完善，还得补充其它策略才行。
2
分析一下：
1)第一行就是模式串的各个字符，第二行是数组的标号，因为到时候会定义一个next[5]数组存放表格中的信息。
2)"前后缀等"表示的是包含比较失败字符串在内的字符前后缀相等的最大字符长度，而next值是前后缀向右填充并在前面补-1得到的数组值。结合下图和表格中的数据字符对应的next值是对应得上的。
3)那么我们可以检验一下，字符C比较失败以后从匹配字符[2]继续匹配，即模式串的第三个字符，跟之前的分析一致。
4)同样我们来看看aaaac模式串的next数组图:
5)同样加入我们在第3个a匹配失败和最后一个c匹配失败以后如何获得前后缀的呢?如下图所示，前面的例子没有重叠的前后缀出现，不过这里就出现了重叠的问题。
6)很明显如果字符C匹配失败，对应的需要从模式串[3]继续比较，即模式串的第四个字符继续比较，与前面的分析一致。
7)如果大家还看不懂前后缀，那bug菌再画一个图，你肯定就懂了:
4、KMP算法的C实现
1
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5#define NEXT_LEN 6
6
7char *Parent = "1234567891212123456789";
8char *Chind = "121212";
9int next[NEXT_LEN] = {0};
10
11/******************************************************
12 * Fuction：KMP匹配算法查询函数
13 * Params : str1:主串；str2:模式串；next:next数组
14 * (公众号 : 最后一个bug)
15 *****************************************************/
16char* KMP(const char * str1, const char * str2,int * next)
17{
18 int i = 0;
19 int j = 0;
20 char * ret = (char*)str1;
21
22 while (i < strlen(str1) && j < (int)strlen(str2)) //主串结束、模式串成功
23 {
24 //j = -1直接到next[0]处理或者字符匹配成功
25 if ((j == -1)||(str1[i] == str2[j]))
26 {
27 //下一个字符移动
28 i++;
29 j++;
30 }
31 else
32 {
33 //如果匹配不成功通过j(模式串比较失败地址)找到next中下一次与主串比较的模式串地址
34 j = next[j];
35 }
36 }
37
38 if (j == strlen(str2))//表示的是模式串全部匹配
39 {
40 return (ret + i - j);
41 }
42 else
43 return(NULL);
44}
45/******************************************************
46 * Fuction：KMP匹配算法next数组生成
47 * Params : str:模式串；next:next数组
48 * (公众号 : 最后一个bug)
49 *****************************************************/
50void getNext(const char * str, int * next)
51{
52 next[0] = -1;
53 int i = 0, j = -1;
54
55 while (i < (strlen(str) - 1))
56 {
57 if ((j == -1 )||(str[i] == str[j]))//通过模式串自身对比获得next数组值
58 {
59 ++i;
60 ++j;
61 next[i] = j;
62 }
63 else
64 {
65 j = next[j];
66 }
67 }
68}
69
70/******************************************************
71 * Fuction：暴力匹配算法
72 * Params :str1:主串；str2:模式串
73 * (公众号 : 最后一个bug)
74 *****************************************************/
75char *strstr(const char *str1, const char *str2)
76{
77 char *cp = (char*)str1;
78 char *s1, *s2;
79
80 if (!*str2)
81 return((char *)str1);
82
83 while (*cp)
84 {
85 s1 = cp;
86 s2 = (char *)str2;
87 while (*s1 && *s2 && !(*s1 - *s2))
88 {
89 s1++, s2++;
90 }
91
92 if (!*s2)
93 return(cp);
94
95 cp++;
96 }
97 return(NULL);
98}
99
100/******************************************************
101 * Fuction：对比主函数
102 * Author : (公众号 : 最后一个bug)
103 *****************************************************/
104int main(int argc, char *argv[]) {
105 int result = 0;
106 int i = 0;
107 //获得KMP的next数组
108 getNext(Chind,next);
109 for( i = 0; i < NEXT_LEN;i++)
110 {
111 printf("Next[%d] = %d\n",i,next[i]);
112 }
113 //进行KMP匹配
114 result = KMP(Parent,Chind,next)- Parent;
115 printf("KMP result = %d\n",result);
116 //进行暴力匹配
117 result = strstr(Parent,Chind) - Parent;
118 printf("strstr result = %d\n",result);
119
120 return 0;
121}
运行结果如下：
分析一下：
大家仔细阅读了会发现，其实求next数组和KMP匹配算法是非常的相似，KMP算法的关键就是求next数组，一旦匹配不成功就会去next数组中找下一个模式串的匹配点，再次拿着该匹配点与匹配失败主串进行比较.
所以KMP算法的优越之处在于不再需要重头开始比较，其主串的比较指针是不会倒退的。至于两个算法的时间上的复杂度KMP<strstr，这一部分的推导bug菌就不深入分析了，大家有时间可以查阅一下相关资料进行进一步阅读和学习，具体的应用bug菌在前面的暴力匹配有跟大家讲解过，这里就不在赘述了。
5、最后小结
KMP算法就跟大家介绍到这里了，希望大家能有新的收获，算法的话大家也不需要死记硬背，基本到处都能够找到，了解原理并且能够获得这种处理问题的思维就达到学习的目的了。
评论