高效"KMP"字符匹配算法就這么簡(jiǎn)單
1、聊一聊
上一篇文章
"暴力"字符匹配算法的C語(yǔ)言實(shí)現(xiàn)
2、KMP算法介紹
1
2
3、原理分析
1
按照之前的做法，如果已經(jīng)匹配過(guò)的aaaa中前兩個(gè)字節(jié)等于后兩個(gè)字節(jié)，那么模式串應(yīng)該移動(dòng)兩個(gè)字節(jié)，然而我們發(fā)現(xiàn)其只需要移動(dòng)一個(gè)字節(jié)就能匹配成功了，看來(lái)僅僅用之前的策略還不夠完善，還得補(bǔ)充其它策略才行。
2
分析一下：
1)第一行就是模式串的各個(gè)字符，第二行是數(shù)組的標(biāo)號(hào)，因?yàn)榈綍r(shí)候會(huì)定義一個(gè)next[5]數(shù)組存放表格中的信息。
2)"前后綴等"表示的是包含比較失敗字符串在內(nèi)的字符前后綴相等的最大字符長(zhǎng)度，而next值是前后綴向右填充并在前面補(bǔ)-1得到的數(shù)組值。結(jié)合下圖和表格中的數(shù)據(jù)字符對(duì)應(yīng)的next值是對(duì)應(yīng)得上的。
3)那么我們可以檢驗(yàn)一下，字符C比較失敗以后從匹配字符[2]繼續(xù)匹配，即模式串的第三個(gè)字符，跟之前的分析一致。
4)同樣我們來(lái)看看aaaac模式串的next數(shù)組圖:
5)同樣加入我們?cè)诘?個(gè)a匹配失敗和最后一個(gè)c匹配失敗以后如何獲得前后綴的呢?如下圖所示，前面的例子沒(méi)有重疊的前后綴出現(xiàn)，不過(guò)這里就出現(xiàn)了重疊的問(wèn)題。
6)很明顯如果字符C匹配失敗，對(duì)應(yīng)的需要從模式串[3]繼續(xù)比較，即模式串的第四個(gè)字符繼續(xù)比較，與前面的分析一致。
7)如果大家還看不懂前后綴，那bug菌再畫(huà)一個(gè)圖，你肯定就懂了:
4、KMP算法的C實(shí)現(xiàn)
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匹配算法查詢(xún)函數(shù)
13 * Params : str1:主串；str2:模式串；next:next數(shù)組
14 * (公眾號(hào) : 最后一個(gè)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)) //主串結(jié)束、模式串成功
23 {
24 //j = -1直接到next[0]處理或者字符匹配成功
25 if ((j == -1)||(str1[i] == str2[j]))
26 {
27 //下一個(gè)字符移動(dòng)
28 i++;
29 j++;
30 }
31 else
32 {
33 //如果匹配不成功通過(guò)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數(shù)組生成
47 * Params : str:模式串；next:next數(shù)組
48 * (公眾號(hào) : 最后一個(gè)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]))//通過(guò)模式串自身對(duì)比獲得next數(shù)組值
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 * (公眾號(hào) : 最后一個(gè)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：對(duì)比主函數(shù)
102 * Author : (公眾號(hào) : 最后一個(gè)bug)
103 *****************************************************/
104int main(int argc, char *argv[]) {
105 int result = 0;
106 int i = 0;
107 //獲得KMP的next數(shù)組
108 getNext(Chind,next);
109 for( i = 0; i < NEXT_LEN;i++)
110 {
111 printf("Next[%d] = %d\n",i,next[i]);
112 }
113 //進(jìn)行KMP匹配
114 result = KMP(Parent,Chind,next)- Parent;
115 printf("KMP result = %d\n",result);
116 //進(jìn)行暴力匹配
117 result = strstr(Parent,Chind) - Parent;
118 printf("strstr result = %d\n",result);
119
120 return 0;
121}
運(yùn)行結(jié)果如下：
分析一下：
大家仔細(xì)閱讀了會(huì)發(fā)現(xiàn)，其實(shí)求next數(shù)組和KMP匹配算法是非常的相似，KMP算法的關(guān)鍵就是求next數(shù)組，一旦匹配不成功就會(huì)去next數(shù)組中找下一個(gè)模式串的匹配點(diǎn)，再次拿著該匹配點(diǎn)與匹配失敗主串進(jìn)行比較.
所以KMP算法的優(yōu)越之處在于不再需要重頭開(kāi)始比較，其主串的比較指針是不會(huì)倒退的。至于兩個(gè)算法的時(shí)間上的復(fù)雜度KMP<strstr，這一部分的推導(dǎo)bug菌就不深入分析了，大家有時(shí)間可以查閱一下相關(guān)資料進(jìn)行進(jìn)一步閱讀和學(xué)習(xí)，具體的應(yīng)用bug菌在前面的暴力匹配有跟大家講解過(guò)，這里就不在贅述了。
5、最后小結(jié)
KMP算法就跟大家介紹到這里了，希望大家能有新的收獲，算法的話大家也不需要死記硬背，基本到處都能夠找到，了解原理并且能夠獲得這種處理問(wèn)題的思維就達(dá)到學(xué)習(xí)的目的了。
