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

【数据结构】数组和字符串(十四):字符串匹配1:朴素的模式匹配算法(StringMatching)

文章目录

  • 4.3 字符串
    • 4.3.1 字符串的定义与存储
    • 4.3.2 字符串的基本操作
    • 4.3.3 模式匹配算法
      • 1. 算法原理
      • 2. ADL语言
      • 3. 伪代码
      • 4. C语言实现
      • 5 时间复杂度

4.3 字符串

  字符串(String)是由零个或多个字符(char)顺序排列组成的有限序列,简称为串。例如 “good morning”就是由12个字符构成的一个字符串。一般把字符串记作:

S = ′ ′ a 0 a 1 … a n − 1 ′ ′ S=''a_{0} a_{1}…a_{n-1}'' S=′′a0a1an1′′

  其中S是串名,引号中的字符序列是串值。字符个数是串的长度,长度为0的串被称为空串,因为它不包含任何字符。需要注意的是,空格字符(" ")并不是空串,因为它包含一个字符——空格。
  若把某个串称为主串,则主串中任意个连续的字符组成的子序列被称为子串。子串在主串中第一次出现时,其首字符在主串中的序号被称为该子串在主串中的位置。
  关于字符串的基础知识亦可参考前文:
【重拾C语言】六、批量数据组织(三)数组初值;字符串、字符数组、字符串数组;类型定义 typedef
【重拾C语言】七、指针(三)指针与字符串(字符串与字符串数组;指针与字符串的遍历、拷贝、比较;反转字符串

4.3.1 字符串的定义与存储

  字符串在许多非数值计算问题中扮演着重要的角色,并在模式匹配、程序编译和数据处理等领域得到广泛应用。在高级程序设计语言中,字符串通常被定义为以特殊字符’\0’(称为空字符或字符串结束符)结尾的字符序列。这个约定使得在处理字符串时可以方便地确定字符串的结束位置。关于字符串的存储方式,主要有两种常见的方式:

  • 顺序存储:字符串的字符按照顺序依次存储在连续的内存空间中。这种方式使得字符串的访问和操作效率较高,可以通过索引直接访问任意位置的字符。在顺序存储方式中,字符串的长度可以通过计算字符个数或者遇到’\0’结束符来确定。

  • 链式存储:字符串的字符通过链表的方式进行存储。每个节点包含一个字符和指向下一个节点的指针。链式存储方式可以动态地分配内存,适用于长度可变的字符串。但是相比于顺序存储,链式存储方式需要更多的内存空间,并且访问字符需要遍历链表。

  选择何种存储方式取决于具体的应用场景和需求。顺序存储适合于需要频繁访问和操作字符串的情况,而链式存储适合于长度可变的字符串或者对内存空间要求较高的情况。具体C语言实现可参照前文:
  【数据结构】数组和字符串(十一):字符串的定义与存储(顺序存储、链式存储及其C语言实现)

4.3.2 字符串的基本操作

顺序存储:【数据结构】数组和字符串(十二):顺序存储字符串的基本操作(串长统计、查找、复制、插入、删除、串拼接)
链式存储:【数据结构】数组和字符串(十三):链式字符串的基本操作(串长统计、查找、复制、插入、删除、串拼接)

4.3.3 模式匹配算法

  文本编辑器中常用的“查找”、“替换”和“全部替换”等基本的编辑操作就是最普通的模式匹配问题,即:在文本文件中查找串。它的查找过程可简单描述如下:给定两个字符串变量 S 和 P,其中目标串 S 有n个字符,模式串P有m个字符,m≤n . 从S的给定位置(通常为S的第一个字符)开始,搜索模式串P,如果找到,返回模式串P在S中匹配成功的起始位置;如果没找到(即S中没有P),则返回–1 .
  字符串匹配可以采用多种算法,包括朴素模式匹配算法、KMP(Knuth-Morris-Pratt)算法、Boyer-Moore算法等。这些算法的性能和效率各不相同,具体选择取决于应用的需求和文本数据的规模。

1. 算法原理

  • 从S的字符 S 0 S_{0} S0开始,将P(长度为m)中的字符依次与S中的字符进行比较:
    • S 0 = P 0 , S 1 = P 1 , … , S m − 1 = P m − 1 S_{0}=P_{0},S_{1}=P_{1},…,S_{m-1}=P_{m-1} S0=P0S1=P1Sm1=Pm1则匹配成功,返回与 P 0 P_{0} P0相匹配的字符 S 0 S_{0} S0 S S S中的位置(下标为0);
    • 若某一步, S i ≠ P i S_{i}≠P_{i} Si=Pi,说明此次匹配不成功,以下比较无需进行。
  • 于是再从 S S S的字符 S 1 S_{1} S1开始进行第二次匹配,重复刚才的步骤
    • 看是否有 S 1 = P 0 , S 2 = P 1 , … , S m = P m − 1 S_{1}=P_{0},S_{2}=P_{1},…,S_{m}=P_{m-1} S1=P0S2=P1Sm=Pm1 若匹配成功,返回与P0相匹配的字符S1在S中的下标1.
    • 否则从S的字符S2开始进行第三次匹配’
  • ……
  • 若第 n − m + 1 n-m+1 nm+1次匹配(即最后一次匹配)仍得不到 S n − m = P 0 , S n − m + 1 = P 1 , … , S n − 1 = P m − 1 S_{n-m}=P_{0},S_{n-m+1}=P_{1},…,S_{n-1}=P_{m-1} Snm=P0Snm+1=P1Sn1=Pm1,说明匹配失败,返回 -1 .
  • 这种模式匹配算法被称为朴素的模式匹配算法

2. ADL语言

在这里插入图片描述

3. 伪代码

function naivePatternMatching(S, P):n = length(S)  # 目标串的长度m = length(P)  # 模式串的长度for i from 0 to n - m:j = 0while j < m and S[i + j] == P[j]:j = j + 1if j == m:  # 如果模式串完全匹配return i  # 返回匹配位置return -1  # 未找到匹配# 示例用法
S = "ABABCABAB"
P = "ABAB"
result = naivePatternMatching(S, P)
if result != -1:print("模式串在目标串中的位置:", result)
else:print("未找到匹配")

4. C语言实现

#include <stdio.h>
#include <string.h>int naivePatternMatching(const char* S, const char* P) {int n = strlen(S);  // 目标串的长度int m = strlen(P);  // 模式串的长度for (int i = 0; i <= n - m; i++) {int j = 0;while (j < m && S[i + j] == P[j]) {j++;}if (j == m) {  // 如果模式串完全匹配return i;  // 返回匹配位置}}return -1;  // 未找到匹配
}int main() {const char* S = "QomolangmaH";const char* P = "lang";
//    const char* P = "gan";int result = naivePatternMatching(S, P);if (result != -1) {printf("模式串在目标串中的位置: %d\n", result);} else {printf("未找到匹配\n");}return 0;
}

在这里插入图片描述

在这里插入图片描述

5 时间复杂度

  朴素模式匹配算法的优点是过程简单,缺点是效率低。在最坏情况下,该算法要匹配n-m+1次,每次匹配要做m次比较,因此最坏情况下的比较次数是m×(n-m+1),时间复杂性为O(m×(n-m+1)),通常情况下,m的值远小于n的值,于是最坏情况下的时间复杂性可粗略地记为O(n×m)。对于长文本和模式串,可能会导致性能问题。因此,有更高效的模式匹配算法,如KMPBoyer-Moore等,用于更快速地找到匹配位置,具体内容详见后文。

相关文章:

【数据结构】数组和字符串(十四):字符串匹配1:朴素的模式匹配算法(StringMatching)

文章目录 4.3 字符串4.3.1 字符串的定义与存储4.3.2 字符串的基本操作4.3.3 模式匹配算法1. 算法原理2. ADL语言3. 伪代码4. C语言实现5 时间复杂度 4.3 字符串 字符串(String)是由零个或多个字符(char)顺序排列组成的有限序列&#xff0c;简称为串。例如 “good morning”就是…...

VMWare虚拟机问题

镜像下载 阿里巴巴开源镜像站-OPSX镜像站-阿里云开发者社区...

代码随想录算法训练营第23期day39 |62.不同路径、63. 不同路径 II

目录 一、&#xff08;leetcode 62&#xff09;不同路径 1.动态规划 1&#xff09;确定dp数组&#xff08;dp table&#xff09;以及下标的含义 2&#xff09;确定递推公式 3&#xff09;dp数组的初始化 4&#xff09;确定遍历顺序 5&#xff09;举例推导dp数组 2.数论方…...

白帽黑客入门,“每天一个黑客技巧”实现黑客的自我突破 !(附工具包!)

年底了&#xff0c;不少朋友都是在总结一年的学习成果。最后发现完成情况与自己最初定下的目标相去甚远。 同时也针对粉丝和网上大部分存在的问题进行了整理&#xff1a; “为什么我感觉学安全好难&#xff1f;” “渗透测试到底该怎么学&#xff1f;” “为什么总是挖不到漏…...

Jmeter参数化 —— 循环断言多方法

1、参数化接口测试数据 注意&#xff1a;csv文档参数化&#xff0c;里面有多少条数据&#xff0c;就要在线程组里循环多少次&#xff0c;不然就只执行一次 2、添加配置元件-计数器 关于计数器 ①Starting Value&#xff1a;给定计数器的初始值; ②递增&#xff1a;每次循环迭代…...

Autosar诊断实战系列26-Dem(DTCEvent)要点及配置开发详解

本文框架 前言1. Dem及其与其他模块交互介绍1.1 与DCM模块交互1.1.1 0x14服务调用时序1.1.2 0x85服务调用时序1.1.3 0x19服务调用时序1.2 与Fim模块交互1.3 与NvM模块交互1.4 与BswM模块交互1.5 与其他BSW及APP模块交互2. Dem配置开发介绍2.1 DemGeneral配置2.1.1 DemGeneral一…...

STL(第五课):queue

STL&#xff08;标准模板库&#xff09;是一种C标准库&#xff0c;在其中包含了许多常用的数据结构和算法。其中&#xff0c;queue就是STL库中的一个数据结构&#xff0c;用于实现队列&#xff08;先进先出FIFO&#xff09;。 使用STL queue&#xff0c;需要引入头文件<queu…...

点大商城V2版 2.5.2.1 全开源独立版 多小程序端+unipp安装教程

点大商城V2是一款采用全新界面设计支持多端覆盖的小程序应用&#xff0c;支持H5、微信公众号、微信小程序、头条小程序、支付宝小程序、百度小程序&#xff0c;本程序是点大商城V2独立版&#xff0c;包含全部插件&#xff0c;代码全开源&#xff0c;并且有VUE全端代码。分销&am…...

Redo Log(重做日志)的刷盘策略

1. 概述 Redo Log&#xff08;重做日志&#xff09;是 InnoDB 存储引擎中的一种关键组件&#xff0c;用于保障数据库事务的持久性和崩溃恢复。InnoDB 将事务所做的更改先记录到重做日志&#xff0c;之后再将其应用到磁盘上的数据页。 刷盘策略&#xff08;Flush Policy&#x…...

QT窗体之间值的传递,多种方法实现

目录 1. 信号和槽机制 2. 全局变量或单例模式 3. 事件过滤器 4. Qt属性系统 5. 使用QSettings类 在Qt中&#xff0c;有多种方法可以在窗体之间传递值。下面是一些常用的方法&#xff1a; 1. 信号和槽机制 使用Qt的信号和槽机制是一种常见的方式来在窗体之间传递值。您可以…...

政务服务技能竞赛中用到的软件和硬件

政务服务技能竞赛包括争上游、抢先机、秀风采、比擂台几个环节&#xff0c;用到选手端平板、评委端平板、主持人平板、抢答器等设备、抢答器等。分别计算团队分和个人分。答题规则和计分方案均较为复杂&#xff0c;一般竞赛软件无法实现&#xff0c;要用到高端竞赛软件&#xf…...

tcp/ip该来的还是得来

1. TCP/IP、Http、Socket的区别 \qquad 区别是&#xff1a;TCP/IP即传输控制/网络协议&#xff0c;也叫作网络通讯协议&#xff0c;它是在网络的使用中的最基本的通信协议。Http是一个简单的请求-响应协议&#xff0c;它通常运行在TCP之上。Socket是对网络中不同主机上的应用进…...

OpenCV官方教程中文版 —— 图像修复

OpenCV官方教程中文版 —— 图像修复 前言一、基础二、代码三、更多资源 前言 本节我们将要学习&#xff1a; • 使用修补技术去除老照片中小的噪音和划痕 • 使用 OpenCV 中与修补技术相关的函数 一、基础 在我们每个人的家中可能都会几张退化的老照片&#xff0c;有时候…...

前端难学还是后端难学?系统安全,web安全,网络安全是什么区别?

系统安全&#xff0c;web安全&#xff0c;网络安全是什么区别&#xff1f;三无纬度安全问题 系统安全&#xff0c;可以说是电脑软件的安全问题&#xff0c;比如windows经常提示修复漏洞&#xff0c;是一个安全问题 网页安全&#xff0c;网站安全&#xff0c;比如&#xff0c;…...

diffusers-Load pipelines,models,and schedulers

https://huggingface.co/docs/diffusers/using-diffusers/loadinghttps://huggingface.co/docs/diffusers/using-diffusers/loading 有一种简便的方法用于推理是至关重要的。扩散系统通常由多个组件组成&#xff0c;如parameterized model、tokenizers和schedulers&#xff0c…...

私域营销必备:轻松掌握微信CRM管理方法

大家在微信私域营销中都遇到了什么问题&#xff1f; 比如管理时间不够&#xff0c;群发实效性低&#xff0c;自动回复无法适应变化等等。 我们可以利用微信CRM这个工具&#xff0c;轻松解决这些问题。 请问你们最想用这个工具解决什么问题呢&#xff1f; 使用微信CRM不仅可…...

最长回文子串-LeetCode5 动态规划

由于基础还不是很牢固 一时间只能想到暴力的解法: 取遍每个子串 总数量nn-1n-2…1 O(n^2) 判断每个子串是否属于回文串 O(n) 故总时间复杂度为O(n^3) class Solution { public:string longestPalindrome(string s) { int max0;string ret;for(int i0;i<s.size();i)for(int…...

mysql简单备份和恢复

版本&#xff1a;mysql8.0 官方文档 &#xff1a;MySQL :: MySQL 8.0 Reference Manual :: 7 Backup and Recovery 1.物理备份恢复 物理备份是以数据文件形式备份。这种方式效率高点&#xff0c;适合大型数据库备份。物理备份可冷备可热备。 使用mysqlbackup 命令进行物理备…...

JMeter介绍

1. JMeter是什么&#xff1f; 是Apache组织开发基于Java的接口测试工具&#xff0c;性能测试工具 2.JMeter的优缺点 优点&#xff1a; 开源&#xff0c;免费 跨平台 支持多协议 轻量级别 缺点&#xff1a; 不支持IP欺骗 不可验证页面UI 3.JMeter可以用来做什么&#xff1f; …...

flink job同时使用BroadcastProcessFunction和KeyedBroadcastProcessFunction例子

背景&#xff1a; 广播状态可以用于规则表或者配置表的实时更新&#xff0c;本文就是用一个欺诈检测的flink作业作为例子看一下BroadcastProcessFunction和KeyedBroadcastProcessFunction的使用 BroadcastProcessFunction和KeyedBroadcastProcessFunction的使用 1.首先看主流…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...