【字符串匹配】 KMP算法与BM算法的简单c++代码实现

2024-01-15 03:08

本文主要是介绍【字符串匹配】 KMP算法与BM算法的简单c++代码实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

KMP算法使用了比较简洁的代码(Getnext与KMPfind),BM方法只是生搬硬套。。。

class Solution {
public:void Getnext(string t,int l,vector<int>&next){//获取优化next数组int j=0,k=-1;next[0]=-1;while(j<l-1){if(k == -1 || t[j] == t[k]){j++;k++;if(t[j]==t[k])//当两个字符相同时,就跳过next[j] = next[k];elsenext[j] = k;}else k = next[k];}}int KMPfind(string target,string pattern){//KMP字符串匹配int l=pattern.size();int L=target.size();vector<int>next(l);Getnext(pattern,l,next);int i=0,j=0;while(i<L&&j<l){if(j==-1||target[i]==pattern[j]){i++;j++;}else j=next[j];}if(j>=l)return i-l;else return -1;}int BMfind(string target,string pattern){//BM算法的一种实现int l=pattern.size();//构造坏字符跳转规则vector<int>skip1(26);for(int i=0;i<26;i++)skip1[i]=l;for(int i=0;i<l;i++){skip1[pattern[i]-'a']=l-1-i;}//构造好后缀跳转规则vector<int>skip2(l);//跳转数组vector<int>pre(l);//包含后缀位置数组for(int i=0;i<l;i++)pre[i]=l;skip2[l-1]=1;int c=0;for(int i = l -1; i>0; i--){for(int j = 0; j < i; j++){if(pattern.substr(j,l-i)==pattern.substr(i,l-i)){if(j == 0){c = l - i;pre[i-1]=-1;}else{if(pattern[i - 1] != pattern[j - 1])pre[i - 1] = j - 1;}}}}for(int i = 0; i < l - 1; i++){if(pre[i] != l)skip2[i] = l - 1 - pre[i];else{skip2[i] = l - 1 - i + pre[i];if(c != 0 && l - 1 - i >= c)skip2[i] -= c;}}//开始匹配int i=l-1;//目标指针int j=l-1;//模式指针int L=target.size();while(i<L){while(j>=0&&(target[i]==pattern[j])){i--;j--;}if(j<0)return i+1;else{i+=max(skip1[target[i]-'a'],skip2[j]);j=l-1;}}return -1;}int strStr(string haystack, string needle) {if(needle=="")return 0;return KMPfind(haystack,needle);}};

这篇关于【字符串匹配】 KMP算法与BM算法的简单c++代码实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python实现终端清屏的几种方式详解

《Python实现终端清屏的几种方式详解》在使用Python进行终端交互式编程时,我们经常需要清空当前终端屏幕的内容,本文为大家整理了几种常见的实现方法,有需要的小伙伴可以参考下... 目录方法一:使用 `os` 模块调用系统命令方法二:使用 `subprocess` 模块执行命令方法三:打印多个换行符模拟

SpringBoot+EasyPOI轻松实现Excel和Word导出PDF

《SpringBoot+EasyPOI轻松实现Excel和Word导出PDF》在企业级开发中,将Excel和Word文档导出为PDF是常见需求,本文将结合​​EasyPOI和​​Aspose系列工具实... 目录一、环境准备与依赖配置1.1 方案选型1.2 依赖配置(商业库方案)二、Excel 导出 PDF

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器(Broker)‌‌3. pytho

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、

使用zip4j实现Java中的ZIP文件加密压缩的操作方法

《使用zip4j实现Java中的ZIP文件加密压缩的操作方法》本文介绍如何通过Maven集成zip4j1.3.2库创建带密码保护的ZIP文件,涵盖依赖配置、代码示例及加密原理,确保数据安全性,感兴趣的... 目录1. zip4j库介绍和版本1.1 zip4j库概述1.2 zip4j的版本演变1.3 zip4

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

Spring StateMachine实现状态机使用示例详解

《SpringStateMachine实现状态机使用示例详解》本文介绍SpringStateMachine实现状态机的步骤,包括依赖导入、枚举定义、状态转移规则配置、上下文管理及服务调用示例,重点解... 目录什么是状态机使用示例什么是状态机状态机是计算机科学中的​​核心建模工具​​,用于描述对象在其生命