在本期的字符串匹配算法中，我将给大家带来常见的两种经典的示例：
- 1、暴力匹配（BF）算法
- 2、KMP算法
（一）暴力匹配（BF）算法
1、思想
BF 算法，即 暴力 (Brute Force) 算法 ，是普通的模式匹配算法， BF 算法的思想：
- 就是将目标串S的第一个字符与模式串T 的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；
- 若不相等，则比较S的第二个字符和 T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。
2、演示
大家看到上诉这段话时肯定是晦涩难懂的，需要例子支持
下面我们就通过例子来解释这个问题：
- 假定我们给出字符串 ”ababcabcdabcde”作为主串， 然后给出子串： ”abcd”；
- 现在我们需要查找子串是否在主串中出现，出现返回主串中的第一个匹配的下标，失败返回-1
- 只要在匹配的过程当中，匹配失败，那么：i回退到刚刚位置的下一个,j回退到0下标重新开始
3、代码展示
int BF(char *str,char *sub) //str:主串 sub:子串 { assert(str != NULL && sub != NULL); if(str == NULL || sub == NULL) { return -1; } int i = 0; int j = 0; int strLen = strlen(str); int subLen = strlen(sub); while(i < strLen && j < subLen) { if(str[i] == sub[j]) { i++; j++; } else { //回退 i = i-j+1; j = 0; } } if(j >= subLen) { return i-j; } return -1; } int main() { printf("%d\n",BF("ababcabcdabcde","abcd")); printf("%d\n",BF("ababcabcdabcde","abcde")); printf("%d\n",BF("ababcabcdabcde","abcdef")); return 0; }
时间复杂度分析：最坏为 O(m*n); m 是主串长度， n 是子串长度
（二）KMP算法
1、思想
KMP 算法是一种改进的字符串匹配算法，由 D.E.Knuth ， J.H.Morris 和 V.R.Pratt 提出的，因此人们称它为克努特 — 莫里斯— 普拉特操作（简称 KMP 算法）。 KMP 算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next() 函数实现， 函数 本身包含了模式串的局部匹配信息。 KMP 算法的 时间复杂度 O(m+n) [1] 。 来自 ------- 百度百科。
2、演示
1️⃣ BF和KMP的区别
区别 ： KMP 和 BF 唯一不一样的地方在，我主串的 i 并不会回退，并且 j 也不会移动到 0 号位置
首先举例，为什么主串不回退？
j 的回退位置
💨 针对上述这样的情况，我们就需要引出next数组
KMP 的精髓就是 next 数组：也就是用 next[j] = k;来表示，不同的 j 来对应一个 K 值， 这个 K 就是你将来要移动的 j 要移动的位置。
2️⃣ K 的值求解
- 1、规则：找到匹配成功部分的两个相等的真子串（不包含本身），一个以下标 0 字符开始，另一个以 j-1 下标字符结尾。
- 2、不管什么数据 next[0] = -1;next[1] = 0;在这里，我们以下标来开始，而说到的第几个第几个是从 1 开始
3️⃣ 求next数组的练习
练习 1： 举例对于”ababcabcdabcde”， 求其的 next 数组？
到这里大家对如何求next数组应该问题不大了，接下来的问题就是，已知next[i] = k;怎么求next[i+1] = ?
如果我们能够通过 next[i] 的值 , 通过一系列转换得到 next[i+1] 得值，那么我们就能够实现这部分。
那该怎么做呢？
- 首先假设： next[i] = k 成立，那么，就有这个式子成立： P0...Pk-1 = Px...Pi-1;得到： P0...Pk-1 = Pi-k..Pi-1;
- 到这一步：我们再假设如果 Pk = Pi;我们可以得到 P0...Pk = Pi-k..Pi;那这个就是 next[i+1] = k+1;
那么： Pk != Pi 呢？
3、代码展示
void GetNext(int *next,const char *sub) { int lensub = strlen(sub); next[0] = -1; next[1] = 0; int i = 2;//下一项 int k = 0;//前一项的K while(i < lensub)//next数组还没有遍历完 { if((k == -1) || sub[k] == sub[i-1]) { next[i] = k+1; i++; k++;//k = k+1???//下一个K的值新的K值 } else { k = next[k]; } } } int KMP(const char *s,const char *sub,int pos) { int i = pos; int j = 0; int lens = strlen(s); int lensub = strlen(sub); int *next = (int *)malloc(lensub*sizeof(int));//和子串一样长 assert(next != NULL); GetNext(next,sub); while(i < lens && j < lensub) { if((j == -1) || (s[i] == sub[j])) { i++; j++; } else { j = next[j]; } } free(next); if(j >= lensub) { return i-j; } else { return -1; } } int main() { char *str = "ababcabcdabcde"; char *sub = "abcd"; printf("%d\n",KMP(str,sub,0)); return 0; }
4、next数组的优化
next 数组的优化，即如何得到 nextval 数组：有如下串：
- aaaaaaaab；
- next 数组是-1,0,1,2,3,4,5,6,7
nextval 是：-1， -1， -1， -1， -1， -1， -1， -1， 7
💨 为什么出现修正后的数组，假设在 5 号处失败了，那退一步还是 a，还是相等，接着退还是 a
练习
模式串 t=‘abcaabbcabcaabdab’ ，该模式串的 next 数组的值为（ D ） ， nextval 数组的值为 （ F ）
A ． 0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2
B ． 0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2
C ． 0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1
D ． 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2
E ． 0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1
F ． 0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1
（三）总结
BF（Brute Force）和KMP（Knuth-Morris-Pratt）算法是两种字符串匹配算法，它们的主要区别在于匹配过程中的策略和效率。
- BF算法：
- BF算法是一种简单直接的字符串匹配算法，也被称为朴素算法。
- 它的思想是从主串中的每个位置开始，逐个比较主串和模式串的字符，直到找到匹配或遍历完所有可能位置。
- 当字符不匹配时，BF算法通过移动主串指针，重新从下一个位置开始匹配。
- BF算法的时间复杂度为O(m*n)，其中m为主串长度，n为模式串长度，最坏情况下需要遍历所有可能的匹配位置。
- 由于BF算法每次只移动一位，对于大规模文本匹配效率较低。
- KMP算法：
- KMP算法是一种高效的字符串匹配算法，通过利用已知信息减少不必要的字符比较次数。
- 它利用模式串自身的特性，在匹配过程中跳过一部分已经匹配的字符，从而提高匹配效率。
- KMP算法包括两个主要步骤：构建最长公共前后缀数组（next数组）和匹配过程。
- 最长公共前后缀数组（next数组）记录了模式串中对于每个位置，匹配失败时应该跳过的字符数。
- 在匹配过程中，当字符不匹配时，KMP算法通过查询next数组获取跳跃位置，而不是重新从头开始比较。
- KMP算法的时间复杂度为O(m+n)，其中m为主串长度，n为模式串长度，通过next数组的优化，可以在匹配过程中跳过一定数量的比较，从而提高效率。
以下是关于上述两种算法的小结：
- 总结起来，BF算法是一种简单直接的字符串匹配算法，逐个比较字符并逐位移动，效率较低；
- 而KMP算法是一种高效的字符串匹配算法，通过构建最长公共前后缀数组和跳跃匹配位置，减少不必要的字符比较次数，提高匹配效率。
- 因此，在大规模文本匹配的应用中，KMP算法通常比BF算法更加高效。
