字符串匹配算法之BF与KMP算法

2024-04-08 23:52
文章标签 算法 字符串 匹配 kmp bf

本文主要是介绍字符串匹配算法之BF与KMP算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

BF算法(暴力匹配算法)

KMP算法

核心思想:

next数组

next数组的优化


BF算法(暴力匹配算法)

#include <assert.h>
int BF(const char* str, const char* 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; //没有匹配返回-1
}int main()
{printf("%d\n", BF("ababcabcdabcde", "abcd")); //5printf("%d\n", BF("ababcabcdabcde", "abcde")); //9printf("%d\n", BF("ababcabcdabcde", "abcdef")); //-1return 0;
}

KMP算法

核心思想:

KMP算法是在BF算法基础上的优化,BF算法中匹配不成功时i和j都要回退,而KMP算法的核心就是匹配失败时,i不回退,而j回退到特定的位置(不一定是0号位置了),然后继续匹配!

问题:为啥i可以不回退, j也不一定非要回退到0号位置??

有了上面的分析,我们的目标就已经很明确了,就是要计算子串的每个位置匹配失败时,j应该回退到哪一个位置,于是就有了我们的next数组!

next数组

next[i] 记录的就是子串匹配到 i 位置时 匹配失败后 i 应该回退的下标

而next数组如何求解呢??? 比如next数组中 i 下标对应的值是几呢??? 那我们只需要看子串中 [0, i-1]这段区间前缀 和 后缀相等的字符串的最长长度, 假如是k, 那么next[i] = k

子串的第一个位置和第二个位置匹配失败时,该位置之前绝不可能用公共子串,所以next[0]和next[1]都应该是0, 但是为了方便后续代码处理,我们将next[0]置成-1

我们现在已经明白了next数组的做用和求法,但问题是上面的next数组是我们肉眼观察求得的,可是计算机并没有上帝视角,如何编程求得next数组呢???

假设已知next[i] = k, 我们能否求得next[i+1]等于多少呢??? 如果可以求出来,由于next[0]和next[1]都是已知的,所以我们只需要从第三个位置开始for循环即可求得next数组~

问题: 已知next[i] = k, 求next[i+1] = 多少??

1.假设p[i] == p[k], 那么next[i+1] = k+1   (p是patten, 指的是子串, 也叫模式串)

证明:

next[i] = k, 说明 p[0] 到 p[k-1] 与 p[x] 到 p[i-1] 这两段字符串是一样的,根据两段字符串长度一样可以求得x,  (k-1-0)+1 = (i-1-x)+1, 求得x=i-k, 所以 p[0]...[k-1] == p[i-k]...p[i-1]

而p[i] == p[k], 则 p[0]...[k] == p[i-k]...p[i], 即 next[i+1] = k+1

2.假设p[i] != p[k], 此时需要做的就是让k回退即可,只需要让k = next[k],一直回退到 p[i] == p[k], 此时next[i+1] = k+1了!!!

如果回退到了0位置,p[i] 仍然不等于 != p[k],  k再 = next[k], k就 == -1了, 此时如果再判断 p[i] == p[k] 就会越界! 所以如果k == -1了,表明next[i+1]也就是0,刚好是k+1, 这就是为啥把next[0]设置成-1的原因, 然后i++, k++继续填充next数组即可

到此为止,我们就把kmp算法的核心都讲解完了,重点就是kmp算法的核心思想与next数组的原理与求法

#include <assert.h>
#include <stdio.h>
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数组还没有遍历完{//注意,讲解原理时我们假设已知next[i],求next[i+1], 但写代码时next[i]是我们要求解的,因此已知next[i-1]if ((k == -1) || sub[k] == sub[i - 1]) {next[i] = k + 1;i++;k++;}else{k = next[k]; //k回退}}
}int KMP(const char* s, const char* sub, int pos) //pos表示从主串的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就会直接变成-1,然后进入if, 此时让j++来到0号位置,i++来到下一个位置继续匹配即可j = next[j]; }}free(next);if (j >= lensub){return i - j;}else{return -1;}
}int main()
{const char* str = "ababcabcdabcde";const char* sub = "abcd";printf("%d\n", KMP(str, sub, 0)); //5return 0;
}
next数组的优化

如果子串中,有大量的重复元素时,next数组就可以优化,因为假设6号下标匹配失败,回退到next[6]也就是5号下标, 此时字符仍然是'a', 依旧会匹配失败,还需要继续回退!!!

 所以我们可以将next数组优化成nextval数组,nextval数组可以根据next数组求得

1.回退到的位置和当前字符一样,就写回退那个位置的nextval值

2.回退到的位置和当前字符不一样,就写当前字符原来的next值

这篇关于字符串匹配算法之BF与KMP算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/886697

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int

hdu 3065 AC自动机 匹配串编号以及出现次数

题意: 仍旧是天朝语题。 Input 第一行,一个整数N(1<=N<=1000),表示病毒特征码的个数。 接下来N行,每行表示一个病毒特征码,特征码字符串长度在1—50之间,并且只包含“英文大写字符”。任意两个病毒特征码,不会完全相同。 在这之后一行,表示“万恶之源”网站源码,源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符(不包括回车)。