C++ | KMP算法模板

news/2024/2/28 16:45:30

next数组初始化

char a[1000006];//原串
char p[1000006];//子串
int pmt[1000006];void getNext(int m){int j=0;pmt[0]=0;for(int i=1;i<m;++i){while(j>0 && p[i]!=p[j])j=pmt[j-1];if(p[i]==p[j])++j;pmt[i]=j;}
}

以下实例基于上述getNext函数及数据结构执行:

实例1:寻找并输出匹配位置

下例代码中,n为原串a长度,m为子串p长度。以原串第一个字母为下标‘0’位置。

void kmp_findstr(int n,int m){getNext(m);for(int i=0,j=0;i<n;i++){while(j && a[i]!=p[j])j=pmt[j-1];if(a[i]==p[j])++j;if(j==m){cout<<i-j+1<<endl;j=pmt[j-1];}}
}

实例2:寻找第一次匹配位置

函数返回原串第一次匹配子串的位置,如果不匹配则返回-1。

int kmp_findfirst(int n,int m){int place=-1;getNext(m);for(int i=0,j=0;i<n;++i){while(j>0 && p[j]!=a[i])j=pmt[j-1];if(p[j]==a[i])++j;if(j==m){place=i-m+1;break;}}return place;
}

实例3:计算匹配次数

int kmp_strcount(int n,int m){int i,j=0,res=0;getNext(m);for(i=0;i<n;++i){while(j>0 && p[j]!=a[i])j=pmt[j-1];if(p[j]==a[i])++j;if(j==m)++res;}return res;
}


PS: 力扣周赛最后一题用到KMP了,直接AC。 😊
顺便附上源代码:

class Solution {
private:char num[1000006];char p[1000006];int kmp_next[1000006];void getNext(int m){int j=0;kmp_next[0]=0;for(int i=1;i<m;++i){while(j>0 && p[i]!=p[j])j=kmp_next[j-1];if(p[i]==p[j])++j;kmp_next[i]=j;}}int kmp(int n,int m){int i,j=0,res=0;getNext(m);for(i=0; i<n; ++i){while(j>0 && p[j]!=num[i])j=kmp_next[j-1];if(p[j]==num[i])++j;if(j==m)++res;}return res;}
public:int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {int n=nums.size(),m=pattern.size();for(int i=0;i<n-1;i+=1){if(nums[i+1]>nums[i])num[i]='a';else if(nums[i+1]==nums[i])num[i]='b';else if(nums[i+1]<nums[i])num[i]='c';}num[n-1]='d';for(int i=0;i<m;i+=1){if(pattern[i]==1)p[i]='a';else if(pattern[i]==0)p[i]='b';else if(pattern[i]==-1)p[i]='c';}int res=kmp(n,m);return res;}
};

http://www.ppmy.cn/news/1350040.html

相关文章

Flink从入门到实践(三):数据实时采集 - Flink MySQL CDC

文章目录 系列文章索引一、概述1、版本匹配2、导包 二、编码实现1、基本使用2、更多配置3、自定义序列化器4、Flink SQL方式 三、踩坑1、The MySQL server has a timezone offset (0 seconds ahead of UTC) which does not match the configured timezone Asia/Shanghai. 参考资…

【JVM篇】ThreadLocal中为什么要使用弱引用

文章目录 &#x1f354;ThreadLocal中为什么要使用弱引用⭐总结 &#x1f354;ThreadLocal中为什么要使用弱引用 ThreadLocal可以在线程中存放线程的本地变量&#xff0c;保证数据的线程安全 ThreadLocal是这样子保存对象的&#xff1a; 在每个线程中&#xff0c;存放了一个…

notepad++成功安装后默认显示英文怎么设置中文界面?

前几天使用电脑华为管家清理电脑后&#xff0c;发现一直使用的notepad软件变回了英文界面&#xff0c;跟刚成功安装的时候一样&#xff0c;那么应该怎么设置为中文界面呢&#xff1f;具体操作如下&#xff1a; 1、打开notepad软件&#xff0c;点击菜单栏“Settings – Prefere…

嵌入式linux驱动开发之网络设备驱动

https://bbs.csdn.net/topics/612247295 简介 Linux网络设备驱动是Linux内核中的一个重要组成部分&#xff0c;它负责网络设备的底层数据传输和设备控制。与字符设备驱动和块设备驱动相比&#xff0c;网络设备驱动的特点和功能如下&#xff1a; 首先&#xff0c;网络设备驱动…

单片机与外设的交互

单片机与外设的交互是嵌入式系统中非常重要的一个基础知识点。单片机是一个集成在同一芯片上的中央处理器、存储器和输入/输出接口,它可以根据用户编写的程序与各种外部设备即外设进行交互。单片机与外设之间的交互主要通过单片机上的输入/输出口(I/O口)来实现。 I/O口的工作原…

类和对象——封装

师从黑马程序员 封装 封装的意义一 在设计类的时候&#xff0c;属性和行为写在一起&#xff0c;表现事物 语法&#xff1a; class 类名{ 访问权限&#xff1a;属性/行为 }&#xff1b; 设计一个圆类&#xff0c;求圆的周长 代码&#xff1a; 示例1&#xff1a; #inc…

【EAI 015】CLIPort: What and Where Pathways for Robotic Manipulation

论文标题&#xff1a;CLIPort: What and Where Pathways for Robotic Manipulation 论文作者&#xff1a;Mohit Shridhar1, Lucas Manuelli, Dieter Fox1 作者单位&#xff1a;University of Washington, NVIDIA 论文原文&#xff1a;https://arxiv.org/abs/2109.12098 论文出处…

安装opencart

一、安装模板 Install SO Emarket Opencart 4 Theme 一&#xff1a;so_emarket_quick2 二&#xff1a;theme package installation 1、installed opencart Default 2、Extensions->Installer->Upload->so_emarket_theme_oc4011_home21_to_home35_v2.0.3->so_theme…

奶茶点餐|奶茶店自助点餐系统|基于微信小程序的饮品点单系统的设计与实现(源码+数据库+文档)

奶茶店自助点餐系统目录 目录 基于微信小程序的饮品点单系统的设计与实现 一、前言 二、系统功能设计 三、系统实现 1、商品信息管理 2、商品评价管理 3、商品订单管理 4、用户管理 四、数据库设计 1、实体ER图 2、具体的表设计如下所示&#xff1a; 五、核心代码 …

CSS Selector—选择方法,和html自动——异步社区的爬取(动态网页)——爬虫(get和post的区别)

这里先说一下GET请求和POST请求&#xff1a; post我们平时是要加data的也就是信息&#xff0c;你会发现我们平时百度之类的 搜索都是post请求 get我们带的是params&#xff0c;是发送我们指定的内容。 要注意是get和post请求&#xff01;&#xff01;&#xff01; 先说一下异…

跟着cherno手搓游戏引擎【24】开启2D引擎前的项目总结(包括前置知识汇总)

前置技术&#xff1a; vs属性解释&#xff1a; MSBuild的入门完整教程&#xff08;包学包会&#xff09;-CSDN博客 配置界面&#xff1a; c动态链接和静态链接&#xff1a; 隐藏的细节&#xff1a;编译与链接_哔哩哔哩_bilibili 【底层】动态链接库(dll)是如何工作的&…

基于微信小程序的在线课堂的研究与实现,附源码

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝30W、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…

FTP服务简介(工作原理、连接模式、流行服务器软件)

FTP&#xff08;File Transfer Protocol&#xff0c;文件传输服务&#xff09;提供在Internet上的任意两台计算机之间相互进行的文件传输。只要双方主机都支持FTP协议&#xff0c;就可以利用FTP来进行文件传输。 工作原理 FTP服务是客户/服务器模式&#xff0c;用户通过客户机…

[C#] 如何使用ScottPlot.WPF在WPF桌面程序中绘制图表

什么是ScottPlot.WPF&#xff1f; ScottPlot.WPF 是一个开源的数据可视化库&#xff0c;用于在 WPF 应用程序中创建高品质的绘图和图表。它是基于 ScottPlot 库的 WPF 版本&#xff0c;提供了简单易用的 API&#xff0c;使开发人员能够通过简单的代码创建各种类型的图表&#…

第三百一十五回

文章目录 1. 概念介绍2. 基本用法3. 补充用法4. 内容总结 我们在上一章回中介绍了"再谈ListView中的分隔线"&#xff0c;本章回中将介绍showMenu的用法.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1. 概念介绍 我们在第一百六十三回中介绍了showMenu相关的内容…

【设计模式】23中设计模式笔记

设计模式分类 模板方法模式 核心就是设计一个部分抽象类。 这个类具有少量具体的方法&#xff0c;和大量抽象的方法&#xff0c;具体的方法是为外界提供服务的点&#xff0c;具体方法中定义了抽象方法的执行序列 装饰器模式 现在有一个对象A&#xff0c;希望A的a方法被修饰 …

MySQL-----DCL基础操作

▶ DCL简介 DCL英文全称是Data ControlLanguage(数据控制语言)&#xff0c;用来管理数据库用户、控制数据库的访问权限。 DCL--管理用户 ▶ 查询用户 use mysql; select * from user; ▶ 创建用户 ▶ 语法 create user 用户名主机名 identified by 密码 设置为在任意主机上访问…

[自然语言处理|NLP] 文本分类与情感分析,数据预处理流程,包括了同义词替换和拼写纠正,以及使用NLTK库和TextBlob库进行标记化和情感分析(附代码)

[自然语言处理|NLP] 文本分类与情感分析,数据预处理流程,包括了同义词替换和拼写纠正,以及使用NLTK库和TextBlob库进行标记化和情感分析(附代码)。 自然语言处理(Natural Language Processing,简称NLP)是人工智能领域的一个重要分支,涉及了处理和理解人类语言的技术…

快速手动完成 VS 编写脚本自动化:如何选取最高效的工作方式?

那些不懂技术的朋友们可能会觉得&#xff0c;写代码写脚本不就是敲敲键盘嘛&#xff0c;搞那么高科技做什么&#xff0c;直接手工点点鼠标不就完事了。 这种看法很常见&#xff0c;但实际情况要复杂得多。 首先&#xff0c;手工操作虽然对于短期和小规模的任务来说似乎更快&am…

springboot177健身房管理系统

简介 【毕设源码推荐 javaweb 项目】基于springbootvue 的 适用于计算机类毕业设计&#xff0c;课程设计参考与学习用途。仅供学习参考&#xff0c; 不得用于商业或者非法用途&#xff0c;否则&#xff0c;一切后果请用户自负。 看运行截图看 第五章 第四章 获取资料方式 **项…
最新文章