BF、kmp以及Gkmp算法
一、描述：
BF、KMP、GKMP（优化后的kmp）都是基于单个字符串（多个字符串一般要用到其他算法，比如说AC自动机）匹配的算法，不过时间复杂度各有不同，其中BF的时间复杂度为O(n * (m - n + 1))，而kmp算法的时间复杂度为O(n + m)，可见快上了不少，但是这其中确实还是有不足之处，故而推出了优化后的kmp解决了回溯的重复问题。
二、BF算法分析：
BF（bruteforce）是一种暴力的模式匹配算法，其基本原理就是枚举每一种可能发生的情况，直到匹配成功，其花费的时间成本是较高的。下面我们来分析一下具体的实现过程。
首先我们有两个字符串，暂且称第一个长串为主串，称第二个短串为匹配串（子串）
T1：abcdac
T2： dac
第一轮匹配（失败）
第二轮匹配（失败）
第三轮匹配（失败）
第四轮匹配（成功，退出匹配）
代码实现：
1 #include "stdio.h" 2 #include "string.h" 3 int main() 4 { 5 char p[110];//主串 6 char q[110];//子串 7 scanf("%s%s",p,q); 8 int len1 = strlen(p); 9 int len2 = strlen(q); 10 for(int i = 0;i < len1;i++){ 11 int j = 0,m = i; 12 while(j < len2 && m < len1){ 13 if(p[m] != q[j]) 14 break; 15 m++,j++; 16 } 17 if(j == len2) 18 printf("Match Successful in %d\n",i + 1); 19 } 20 return 0; 21 }
三、KMP算法分析：
如果是长度比较短的字符串，我们可能能接受那个时间复杂度，但如果字符串的长度达到了上百万，模式串也有十万，那么匹配的时间将会是一个大麻烦，为此三位学者共同开发了这套快速的字符串匹配算法，根据他们的名字，KMP算法也由此而来。现在让我们来看看这个算法到底巧在什么地方吧！
首先给定两个字符串T1和T2
T1：abaababa
T2：abab
分析可知我们匹配这个字符串按照BF匹配的话，如果其中一个字符不匹配那么我们需要回到开头重新匹配，但是kmp算法充分利用了已知条件----T2，根据T2我们能知道某些一定不能匹配成功的位置，故可以省略，当匹配不成功的时候我们就不需要回到T2的开头重新匹配了，我们可以回到某个位置匹配，为什么呢？因为前面的位置你已经走过了呀，你已经知道哪些位置一定不可能成功匹配了，那如何能让计算机也知道呢？
首先1.我们构建一个next数组，存储不匹配时应该回到的位置（实际上就是该字符上的前缀和后缀的最大相似度+1）
2.构建一个查询函数，当j不满足匹配条件时，根据next数组回溯
虽然构建next数组时会显得浪费了时间，但是在后面查询的时候，将会带来线性阶的回馈。
接下来我们先说说什么是前缀和后缀吧
所谓前缀，就是一个字符串除了最后一个字符不参与组成子串的集合
所谓后缀，就是一个字符串除了第一个字符不参与组成子串的集合
举个例子：
abcd 前缀有a ab abc
后缀有d cd bcd
图片例子：
解释了前缀和后缀，我们来徒手建立个next数组把
T1：abaababa
T2：abab
next【5】：0 1 2 3
又因为a没有前缀也没有后缀，故先给他定为-1，专门处理回溯到子串头的匹配情况
遍历到b
前缀：a
后缀：b
前后缀相似度为0，故next[1] = 1
遍历到a
前缀：a，ab
后缀：b，ab
前后缀最大相似度为2，故next[2] = 3
遍历到b
前缀：a，ab，aba
后缀：b，ab，bab
前后缀最大相似度为2，故next[3] = 3
next数组已经构建好了，那么我么如何匹配呢？
1.碰到相等的时候i，j同时往后走
2.碰到不相等的时候j开始查询next数组回溯，直到走到那些能匹配的位置，或者是返回开头重新匹配
3.如果j已经走到子串尾后一位了，说明已经匹配成功了
代码实现：
1 #include "stdio.h" 2 #include "string.h" 3 int next[100];//next数组存的值实际上就是这个字符的前缀和后缀相似度+1 4 void Get_next(char *q) 5 { 6 int len = strlen(q);//计算模式串长度 7 next[0] = -1;//第一个字符没有前缀也没有后缀故为0 8 int i = 0,k = -1; 9 while(i < len - 1){ 10 if(k == -1 || q[i] == q[k]){//k == -1说明当前字符的前缀和后缀相似度为0，下次匹配得从头开始匹配， 11 k++; 12 i++; 13 next[i] = k; 14 } 15 else 16 k = next[k];//回溯位置 17 } 18 } 19 int kmp(char *p,char *q) 20 { 21 int len1 = strlen(p); 22 int len2 = strlen(q); 23 int i,j; 24 i = j = 0; 25 while(i < len1 && j < len2){ 26 if(j == -1 || p[i] == q[j]){ 27 i++; 28 j++; 29 } 30 else 31 j = next[j]; 32 } 33 if(j == len2) 34 return i - len2; 35 return -1; 36 } 37 int main() 38 { 39 char p[100]; 40 char q[100]; 41 scanf("%s %s",p,q);//先输入主串，再输入模式串 42 Get_next(q); 43 int L = kmp(p,q); 44 if(L != -1) 45 printf("Match successful in %d\n",L + 1); 46 else 47 printf("Match fail!"); 48 return 0; 49 }
四、Gkmp算法分析（优化后的kmp算法）
话说kmp算法已经这么好了，为什么还需要优化呢？因为kmp会执行不必要的回溯过程
比如说：
aaaaxbaaaaab
aaaaab
当第五个a失配后，会回溯到第四个
第四个很显然也会失配，会回溯到第三个a
依次类推就会回到开头了，其实这些过程都是不必要的
所以我们想如果前面的和当前字符相等时，我们的next值是否可以作优化呢？当然是可以的，当当前字符和前面的字符相等时，可以让当前字符的next值直接等于前面字符得next值，那为什么可以这样做呢？我们想啊，如果我当前字符不能满足匹配，但是我前面的能完成匹配，我是不是可以直接回到上一个和我前后缀相同的地方去？所以这就是优化的本质！
代码实现：
1 #include "stdio.h" 2 #include "string.h" 3 int nextval[110]; 4 void Get_nextval(char *q) 5 { 6 int len = strlen(q); 7 int i = 0,j = -1; 8 nextval[0] = -1;//代表匹配失败回到子串头 9 while(i < len){ 10 if(j == -1 || q[i] == q[j]){ 11 i++,j++; 12 if(q[i] != q[j]) 13 nextval[i] = j;//如果不相等，那么就不能回到j能回溯到的那个位置 14 else 15 nextval[i] = nextval[j];//如果相等，那么就能回到j能回溯到的那个位置 16 } 17 else 18 j = nextval[j];//同kmp一样的回溯 19 } 20 } 21 int Gkmp(char *p,char *q) 22 { 23 int i = 0,j = -1; 24 int len1 = strlen(p); 25 int len2 = strlen(q); 26 while(i < len1 && j < len2){ 27 if(j == -1 || p[i] == q[j]){ 28 i++; 29 j++; 30 } 31 else 32 j = nextval[j];//回溯 33 } 34 if(j == len2) 35 return i - len2 + 1; 36 return -1; 37 } 38 int main() 39 { 40 char p[100];//母串 41 char q[100];//子串 42 scanf("%s%s",p,q); 43 Get_nextval(q); 44 int L = Gkmp(p,q); 45 if(L != -1) 46 printf("Match Successful in %d\n",L); 47 else 48 printf("Match fail!\n"); 49 return 0; 50 }
五、总结
学习也必须要注重实践，“纸上谈兵终觉浅，绝知此事要躬行”。