当前位置: 首页 > news >正文

6. 数据结构—串的匹配算法

1.BF算法(暴力算法)

//模式匹配(暴力算法) 
int Index(SString S,SString T){int i=1,j=1;while(i<=S.length&&j<=T.length){if(S[i]==T[i]){i++;j++;}else{i=i-j+2;  //最开始匹配的位置的后一个j=1;      //从头匹配	}}if(j>T.length)return i-T.length;return return 0; 
}

时间复杂度分析O(mn)

假设主串长度为n,待匹配的串长度为m,则最坏时间复杂度为O(nm)。

主串最多需要匹配n-m+1次,每次最多匹配m次(匹配到最后一个发现不匹配了),

所以也就是(n-m+1)*m=nm-m^2+m,因为一般都是n>>m,所以后面的-m^2+m可以省略,也就是O(nm)的时间复杂度。

tips:时间复杂度除非特别指明,一般就是最坏时间复杂度。

2. KMP算法

next[j]表示:当第j个子串的第i个字符与主串发生失配的时候,跳到子串的next[j]位置重新与主串当前位置进行比较。

tips:next[0]=0,next[1]=1(这两始终保持不变)

时间复杂度:O(m+n)

假设主串长度为n,待匹配的串长度为m,则最坏时间复杂度为O(m+n)。

分为两个大步骤:求next[]和匹配。

求next[]:需要对待匹配串进行一个遍历,也就是,次

匹配:需要对主串进行遍历(不回溯),最多n次。

因此最坏时间复杂度为O(m+n)。

3. KMP进一步优化

简单来说,在next[j]基础上进一步修改,

如果p[j]=p[next[j]],那么next[j]=next[next[j]]。

相关文章:

6. 数据结构—串的匹配算法

1.BF算法(暴力算法) //模式匹配(暴力算法) int Index(SString S,SString T){int i1,j1;while(i<S.length&&j<T.length){if(S[i]T[i]){i;j;}else{ii-j2; //最开始匹配的位置的后一个j1; //从头匹配 }}if(j>T.length)return i-T.length;return return 0…...

九大服务架构性能优化方式

来源&#xff1a;九大服务架构性能优化方式 目录 性能优化九大方式&#xff1a; 缓存 使用什么样的缓存 缓存常见问题 缓存淘汰 缓存数据一致性 并行化处理 批量化处理 数据压缩合并 无锁化 顺序写 分片化 避免请求 池化 异步处理 总结 最近做了一些服务性能优…...

【RabbitMQ】 相关概念 + 工作模式

本文将介绍一些MQ中常见的概念&#xff0c;同时也会简单实现一下RabbitMQ的工作流程。 MQ概念 Message Queue消息队列。是用来存储消息的队列&#xff0c;多用于分布式系统之间的通信。 系统间调用通常有&#xff1a;同步通信和异步通信。MQ就是在异步通信的时候使用的。 同…...

嵌入式学习 ——(Linux高级编程——进程)

目录 一、进程的含义 二、进程和程序的区别 三、进程的作用 四、进程的状态 五、进程的调度与上下文切换 六、查询进程相关命令 七、fork()函数 八、getpid()和getppid()函数 九、面试题解析&#xff1a; 十、应用场合及测试 一、进程的含义 进程指正在运行的程序&a…...

C++练习备忘录

1. 保留两位小数输出格式 #include <iostream> #include <iomanip> using namespace std; int main() {double S 0;S (15 25) * 20 / 2;cout << fixed << setprecision(2) << S;return 0; }2. 设置输出宽度 #include <iostream> #inclu…...

改善工作流

快捷键管理器 打开Editor->Shortcuts查看和编辑Unity中的快捷键 示例 ShiftSpace 窗口最大化 P 选择预制体 进入预制体编辑模式 单一检视窗口 选择组件&#xff0c;选择Properties打开一个窗口&#xff0c;显示组件信息&#xff1b;切换对象&#xff0c;窗口信息不会改变…...

迭代器失效

一、什么是迭代器失效 迭代器的主要作用就是让算法能够不用关心底层数据结构&#xff0c;其底层实际就是一个指针&#xff0c;或者是对指针进行了封装&#xff0c;比如&#xff1a;vector的迭代器就是原生态指针T* 。因此迭代器失效&#xff0c;实际就是迭代器底层对应指针所指…...

@RequestParam @RequestBody @PathVariable 这三个注解对应的前端使用vue的http请求时不同的调用方式

1. RequestParam 用途&#xff1a;用于提取请求参数&#xff0c;常见于GET请求或表单提交。 Vue HTTP 请求示例&#xff1a; // 使用axios发送GET请求 axios.get(/api/users, { params: { id: 1, name: John } }); 2. RequestBody 用途&#xff1a;用于提取请求体…...

SQL - 索引

索引本质上是数据库引擎用来快速查找数据的数据结构&#xff0c;可以显著提高查询的性能&#xff0c;为了加快运行较慢的查询。创建索引 默认索引 create index 索引名 on 表名 (列名); 通过对列名进行创建索引&#xff0c;在查询的时候&#xff0c;数据库就能通过索引找到匹配…...

Oracle23ai新特性FOR LOOP循环控制结构增强

在Oracle数据库中&#xff0c;FOR LOOP是一种常用的循环控制结构&#xff0c;它允许你重复执行一系列语句固定次数或直到满足特定条件为止。然而&#xff0c;标准的Oracle PL/SQL中的FOR LOOP主要用于遍历集合&#xff08;如数组或游标的结果集&#xff09;&#xff0c;而不是像…...

DHU OJ 二维数组

思路及代码 #include<iostream> using namespace std; int main(){ //input 多组 //input M,N int 1< <20 //input M 行 N 列 数据 //initialize listint M, N;while (cin >> M >> N){int list[M][N];for (int i 0; i < M-1; i){for (int j 0; j…...

UDP/TCP --- Socket编程

本篇将使用 Linux 中的系统调用来实现模拟 TCP 和 UDP 的通信过程&#xff0c;其中只对 UDP 和 TCP 进行了简单的介绍&#xff0c;本篇主要实现的是代码&#xff0c;至于 UDP 和 TCP 的详细讲解将会在之后的文章中给出。 本篇给出的 tcp 和 udp 的代码中的 echo 都是测试连接是…...

【C语言】最详细的单链表(两遍包会!)

&#x1f984;个人主页:小米里的大麦-CSDN博客 &#x1f38f;所属专栏:C语言数据结构_小米里的大麦的博客-CSDN博客 &#x1f381;代码托管:黄灿灿/数据结构 (gitee.com) ⚙️操作环境:Visual Studio 2022 目录 一、前言 二、单链表的概念 1. 单链表的特点 2. 单链表的基本…...

QT:VS2019 CMake编译CEF

CEF介绍 CEF作为一个基于Chromium的开源Web浏览器控件&#xff0c;为第三方应用提供了强大的嵌入浏览器支持。其多平台支持、HTML5特性、自定义能力以及多进程架构等特性&#xff0c;使得CEF在浏览器开发、桌面应用、开发工具以及自动化测试等领域得到了广泛应用。 多平台支持…...

day31(8/19)——静态文件共享、playbook

目录 一、ansible模块 script模块 copy模块 使用command模块下载 nfs-utils rpcbind 在被控制的主机上添加static目录&#xff0c;并创建test文件 command模块 service模块 二、playbook 三、playbook编排vsftpd 1、安装 2、卸载 3、启动服务 4、修改配置文件设置不…...

白骑士的C#教学实战项目篇 4.4 游戏开发

系列目录 上一篇&#xff1a;白骑士的C#教学实战项目篇 4.3 Web开发 在这一部分&#xff0c;我们将探索如何使用 Unity 和 C# 开发游戏。游戏开发结合了编程、图形设计和创意&#xff0c;既充满挑战又充满乐趣。通过这一节的学习&#xff0c;您将了解游戏引擎的基础知识&#…...

在Vue工程中开发页面时,发现页面垂直方向出现两个滚动条的处理

在Vue工程中开发页面时&#xff0c;发现页面垂直方向出现两个滚动条 最近在开发页面时&#xff0c;发现页面多了两个滚动条&#xff0c;如图&#xff1a; 原因&#xff1a; 当一个页面的内容高度大于屏幕的高度时就会出现滚动条。一般情况下当一个页面高度大于屏幕高度时&a…...

【C++初阶】:C++入门篇(一)

文章目录 前言一、C命名空间1.1 命名空间的定义1.2 命名空间的使用 二、C的输入和输出2.1 cin和cout的使用 三、缺省参数3.1 缺省参数的分类 四、函数重载4.1 函数重载概念及其条件4.2 C支持函数重载原理 -- 名字修饰 前言 C是在C语言的基础之上&#xff0c;增加了一些面向对象…...

【JAVA CORE_API】Day14 Collection、Iterator、增强for、泛型、List、Set

Collection接口及常用方法 Collection<Object> collection new ArrayList();&#xff1a;实例化ArrayList集合对象&#xff1b; collectionName.add(Object obj);&#xff1a;在集合中增加元素&#xff1b; int sizeName collectionName.size();&#xff1a;获取集合…...

Go更换国内源配置环境变量

背景 要在中国境内下载和使用Go编程语言的包&#xff0c;可以使用国内的Go模块代理来加速下载速度。以下是一些常见的国内Go模块代理源以及如何切换到这些源的方法&#xff1a; 常见国内Go模块代理源 七牛云&#xff08;Qiniu&#xff09; https://goproxy.cn 阿里云&#xff0…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

comfyui 工作流中 图生视频 如何增加视频的长度到5秒

comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗&#xff1f; 在ComfyUI中实现图生视频并延长到5秒&#xff0c;需要结合多个扩展和技巧。以下是完整解决方案&#xff1a; 核心工作流配置&#xff08;24fps下5秒120帧&#xff09; #mermaid-svg-yP…...

嵌入式面试常问问题

以下内容面向嵌入式/系统方向的初学者与面试备考者,全面梳理了以下几大板块,并在每个板块末尾列出常见的面试问答思路,帮助你既能夯实基础,又能应对面试挑战。 一、TCP/IP 协议 1.1 TCP/IP 五层模型概述 链路层(Link Layer) 包括网卡驱动、以太网、Wi‑Fi、PPP 等。负责…...

Win系统权限提升篇UAC绕过DLL劫持未引号路径可控服务全检项目

应用场景&#xff1a; 1、常规某个机器被钓鱼后门攻击后&#xff0c;我们需要做更高权限操作或权限维持等。 2、内网域中某个机器被钓鱼后门攻击后&#xff0c;我们需要对后续内网域做安全测试。 #Win10&11-BypassUAC自动提权-MSF&UACME 为了远程执行目标的exe或者b…...

Copilot for Xcode (iOS的 AI辅助编程)

Copilot for Xcode 简介Copilot下载与安装 体验环境要求下载最新的安装包安装登录系统权限设置 AI辅助编程生成注释代码补全简单需求代码生成辅助编程行间代码生成注释联想 代码生成 总结 简介 尝试使用了Copilot&#xff0c;它能根据上下文补全代码&#xff0c;快速生成常用…...