做那网站好,网络营销的工作岗位,北京工业产品设计公司,网络管理中心网站在本期的字符串匹配算法中#xff0c;我将给大家带来常见的两种经典的示例#xff1a;
1、暴力匹配#xff08;BF#xff09;算法 2、KMP算法 目录
#xff08;一#xff09;暴力匹配#xff08;BF#xff09;算法
1、思想
2、演示
3、代码展示
#xff08;二我将给大家带来常见的两种经典的示例
1、暴力匹配BF算法 2、KMP算法 目录
一暴力匹配BF算法
1、思想
2、演示
3、代码展示
二KMP算法
1、思想
2、演示
1️⃣ BF和KMP的区别 2️⃣ K 的值求解
3️⃣ 求next数组的练习
3、代码展示
4、next数组的优化
三总结 一暴力匹配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-j1;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(mn) [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[i1] ? 如果我们能够通过 next[i] 的值 , 通过一系列转换得到 next[i1] 得值那么我们就能够实现这部分。 那该怎么做呢 首先假设 next[i] k 成立那么就有这个式子成立 P0...Pk-1 Px...Pi-1;得到 P0...Pk-1 Pi-k..Pi-1; 到这一步我们再假设如果 Pk Pi;我们可以得到 P0...Pk Pi-k..Pi;那这个就是 next[i1] k1; 那么 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;//前一项的Kwhile(i lensub)//next数组还没有遍历完{if((k -1) || sub[k] sub[i-1]){next[i] k1;i;k;//k k1???//下一个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 数组有如下串 aaaaaaaabnext 数组是-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 三总结
BFBrute Force和KMPKnuth-Morris-Pratt算法是两种字符串匹配算法它们的主要区别在于匹配过程中的策略和效率。 BF算法 BF算法是一种简单直接的字符串匹配算法也被称为朴素算法。它的思想是从主串中的每个位置开始逐个比较主串和模式串的字符直到找到匹配或遍历完所有可能位置。当字符不匹配时BF算法通过移动主串指针重新从下一个位置开始匹配。BF算法的时间复杂度为O(m*n)其中m为主串长度n为模式串长度最坏情况下需要遍历所有可能的匹配位置。由于BF算法每次只移动一位对于大规模文本匹配效率较低。 KMP算法 KMP算法是一种高效的字符串匹配算法通过利用已知信息减少不必要的字符比较次数。它利用模式串自身的特性在匹配过程中跳过一部分已经匹配的字符从而提高匹配效率。KMP算法包括两个主要步骤构建最长公共前后缀数组next数组和匹配过程。最长公共前后缀数组next数组记录了模式串中对于每个位置匹配失败时应该跳过的字符数。在匹配过程中当字符不匹配时KMP算法通过查询next数组获取跳跃位置而不是重新从头开始比较。KMP算法的时间复杂度为O(mn)其中m为主串长度n为模式串长度通过next数组的优化可以在匹配过程中跳过一定数量的比较从而提高效率。 以下是关于上述两种算法的小结
总结起来BF算法是一种简单直接的字符串匹配算法逐个比较字符并逐位移动效率较低而KMP算法是一种高效的字符串匹配算法通过构建最长公共前后缀数组和跳跃匹配位置减少不必要的字符比较次数提高匹配效率。因此在大规模文本匹配的应用中KMP算法通常比BF算法更加高效。
