【数据结构】串的模式匹配(KMP+朴素模式匹配)

2.串的模式匹配

  • 什么是字符串的模式匹配?

    在主串中找到与模式串相同的子串,并返回其所在位置。

    • 模式串:要匹配的一串。注:子串是主串的一部分,一定在主串中存在,但模式串不一定在主串中找得到。

2.1 朴素模式匹配算法

  • 思路

    暴力求解,一个字符一个字符对比下去。

  • 代码思路

    1.给主串一个指针 i,模式串指针 j,两个指针都指向第一个字符;

    2.若 i 和 j 所指字符相等,i+1,j+1;

    3.若 i 和 j 所指字符不相同,j 回到模式串第一个字符,i 指向下一个子串起始位置;

    4.若 j 超过模式串的长度,则匹配成功。

int Index(SString S,SString T){
    int i=1,j=1; //分别扫描主串和模式串
    while(i<S.length && j<=T.length){
        if(S.ch[i]==T.ch[j]){
            i++;j++; //继续比较后继字符
        }
        else{
            i=i-j+2; //到下一个子串的起始位置
            j=1;
        }
    }
    if(j>T.length)
        return i-T.length;
    else
        return 0;
}
  • 时间复杂度

    最坏情况:每个子串都要对比m个字符,共n-m+1个子串,复杂度= O ( ( n − m + 1 ) m ) = O ( n m ) O((n-m+1)m)=O(nm) O((nm+1)m)=O(nm)

2.2 KMP算法

  • 核心思想

    从模式串本身的结构着手,若已匹配相等的前缀序列中有某个后缀正好是模式串的前缀,则可将模式串向后滑动到与这些相等字符对齐的位置。

    • 设置next数组,next[a]=b意思为:

      ​ 当模式串中第a个元素匹配失败时,令主串指针i不变,模式串指针j=b。

      ​ 即当第a个元素匹配失败时,模式串回溯到第b个元素继续与主串匹配。

    • KMP算法=模式匹配过程+next数组求解

  • 时间复杂度

    O ( m + n ) O(m+n) O(m+n)

    其中,求next数组时间复杂度 O ( m ) O(m) O(m)

    模式匹配过程最坏时间复杂度 O ( n ) O(n) O(n)

2.2.1 模式匹配
  • 模式匹配过程(还未求next数组)

    1.分别设置i和j指针,指向主串和模式串;

    2.如果i和j指针指向的字符相同,i和j都加1;

    3.如果不相同,j回溯到模式串的上一个字符,即j=next[j]

    4.如果j等于0(模式串第一个元素下标为1),则i和j都加1。

    int Index_KMP(SString S,SString T,int next[]){
        int i=1,j=1;
        while(i<=S.length&&j<=T.length){
            if(j==0||S.ch[i]==T.ch[j]){
                i++;
                j++;
            }
            else{
                j=next[j];
            } 
        }
        if(j>T.length)
            return i-T.length;
        else
            return 0;
    }
    
2.2.2 求next数组
  • next数组作用

    当模式串的第j个字符失配时,从模式串的第next[j]个继续往后匹配。

  • next数组手算方法

    1.对于任何模式串:next[1]=0,next[2]=1

    2.对其他的next:在不匹配的位置前,划一条分界线,模式串一步步往后退,直到分界线前能对上,或模式串完全跨过分界线为止。此时j指哪,next数组值就是多少。

    • next[i] 存储的是 T[1:i] 这个子串的最长公共前后缀的长度。
  • next数组的优化

    next数组优化为nextval

    在原next数组基础上,若j对应的模式串元素和next[j]对应的模式串元素相等,则令nextval[j]=nextval[next[j]]

    nextval[1]=0;
    for(int j=2;j<=T.length;j++){
        if(T.ch[next[j]]==T.ch[j])
            nextval[j]=nextval[next[j]];
        else
            nextval[j]=next[j];
    }
    
*完整代码 KMP
#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>

#define MaxSize 99

typedef struct {
	char ch[MaxSize];
	int length;
}SString;

void StrAssign(SString& T, char chars[]) {
	for (int i = 0; i <= strlen(chars); i++)
		T.ch[i+1] = chars[i];
	T.length = strlen(chars);
}

void PrintS(SString S) {
	printf("Str:");
	for (int i = 1; i <= S.length; i++)
		printf("%c", S.ch[i]);
	printf("\n");
}

//KMP模式匹配算法
//S:主串
//T:模式串
int Index_KMP(SString S, SString T, int next[]) {
	int i = 1; //主串S的指针
	int j = 1; //模式串T的指针,数组下标都从1开始
	while (i <= S.length && j <= T.length) {
		if (j == 0 || S.ch[i] == T.ch[j]) { //模式串已到头或当前字符相同
			i++; j++; //继续比较后继字符
		}
		else {
			j = next[j]; //模式串向右移动
		}
	}
	if (j > T.length)
		return i - T.length; //匹配成功
	else
		return 0;
}

//求next数组
void get_next(SString T, int next[]) {
	int i = 1, j = 0;
	next[1] = 0;
	while (i < T.length) {
		if (j == 0 || T.ch[i] == T.ch[j]) { //当前字符与前缀字符相同
			i++; j++;
			next[i] = j; //当前位置的next值为前缀字符个数
		}
		else {
			j = next[j]; //不相同则回溯
		}
	}
}

//next数组优化
void get_nextval(SString T, int nextval[]) {
	int i = 1, j = 0;
	nextval[1] = 0;
	while (i < T.length) {
		if (j == 0 || T.ch[i] == T.ch[j]) { //当前字符与前缀字符相同
			i++; j++;
			if (T.ch[i] != T.ch[j])
				nextval[i] = j; //当前位置的nextval值为前缀字符个数
			else
				nextval[i] = nextval[j]; //如果当前字符与前缀字符相同,则继续向前递归
		}
		else {
			j = nextval[j]; //不相同则回溯
		}
	}
}

int main() {
	SString S, T;
	char s[] = "abcabcde";
	char t[] = "abcd";

	StrAssign(S, s);
	StrAssign(T, t);
	PrintS(S);
	PrintS(T);

	int next[MaxSize];
	get_next(T, next);
	int nextval[MaxSize];
	get_nextval(T, nextval);

	int pos = Index_KMP(S, T, next);
	if (pos != 0) {
		printf("Pattern found at position: %d\n", pos);
	}
	else {
		printf("Pattern not found.\n");
	}

	pos = Index_KMP(S, T, nextval);
	if (pos != 0) {
		printf("Pattern found at position: %d\n", pos);
	}
	else {
		printf("Pattern not found.\n");
	}

	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/460225.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

软件无线电系列——带通信号采样定理

本节目录 一、带通信号采样定理 1、带通信号采样定理的定义 2、带通信号采样定理的证明本节内容 一、带通信号采样定理 1、带通信号采样定理的定义 Nyquist采样定理是对频谱分布在(0,fH)上的基带信号的采样分析的&#xff0c;如果信号的频谱分布在某一限定的频带(fL,fH)上&…

Docker使用(四)Docker常见问题分析和解决收集整理

Docker使用(四)Docker常见问题分析和解决收集整理 五、常见问题 1、 启动异常 【描述】&#xff1a; 【分析】&#xff1a;[rootlocalhost ~]# systemctl status docker 【解决】&#xff1a; &#xff08;1&#xff09;卸载后重新安装&#xff0c;不能解决这个问题。 …

腾讯与字节跳动联合创立萨罗斯网络科技公司 深度整合游戏项目

易采游戏网3月15日消息&#xff1a;抖音集团已将其游戏部门的资产转交给腾讯公司管理&#xff0c;而该部门的员工亦将整体迁移至腾讯新成立的子公司。此举在业界引起了广泛的激烈探讨与深度关注。 据透露&#xff0c;由深圳引力工作室主导的S1手游项目和由江南独力工作室研发的…

鸿蒙Harmony应用开发—ArkTS声明式开发(容器组件:List)

列表包含一系列相同宽度的列表项。适合连续、多行呈现同类数据&#xff0c;例如图片和文本。 说明&#xff1a; 该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。该组件内容区小于一屏时&#xff0c;默认没有回弹效果。…

uniapp uview 头像裁剪组件的问题

当切换页面频繁进出头像裁剪组件u-avatar-cropper.vue 获取同一个设备信息时会出现两种不同的高度具体如下 导致 头像裁剪页面高度出现问题&#xff0c;下方按钮被canvas组件遮盖了 解决方法 在进入这个页面前的一个页面做如下代码操作 直接将设备信息提前获取&#xff0c;保…

【论文翻译】UP-DETR—Unsupervised Pre-training for Detection Transformers

0.论文摘要 摘要——通过Transformer model编码器——解码器架构&#xff0c;用于目标检测的检测Transformer model&#xff08;DETR&#xff09;达到了与Faster R-CNN相比具有竞争力的性能。然而&#xff0c;使用scratch transformers训练&#xff0c;DETR需要大规模的训练数…

android seekbar thumb 上添加进度值并居中

环境&#xff1a;android studio 、java 项目需要在进度条的滑块上显示进度值并居中&#xff0c; UI设计图&#xff1a; 代码实现效果图&#xff1a; 浅色模式&#xff1a; 深色模式&#xff1a; 由于一开始没有自定义seekbar&#xff0c; 使用源码Seekar&#xff0c; 滑块要…

【四 (4)数据可视化之 Ploty Express常用图表及代码实现 】

目录 文章导航一、介绍二、安装Plotly Express三、导入Plotly Express四、占比类图表1、饼图2、环形图3、堆叠条形图4、百分比堆叠条形图 五、比较排序类1、条形图2、漏斗图3、面积漏斗图 六、趋势类图表1、折线图2、多图例折线图3、分列折线图4、面积图5、多图例面积图 七、频…

【回归预测】基于DBO-RF(蜣螂优化算法优化随机森林)的回归预测 多输入单输出【Matlab代码#67】

文章目录 【可更换其他算法&#xff0c;获取资源请见文章第6节&#xff1a;资源获取】1. 随机森林RF算法2. 蜣螂优化算法3. 实验模型4. 部分代码展示5. 仿真结果展示6. 资源获取 【可更换其他算法&#xff0c;获取资源请见文章第6节&#xff1a;资源获取】 1. 随机森林RF算法 …

MM1: Methods, Analysis Insights from Multimodal LLM Pre-training

MM1: Methods, Analysis & Insights from Multimodal LLM Pre-training 相关链接&#xff1a;arxiv 关键字&#xff1a;多模态学习、大型语言模型、预训练、视觉语言连接、混合专家模型 摘要 本文讨论了构建高性能的多模态大型语言模型&#xff08;MLLMs&#xff09;。特别…

[SAP ABAP] 异常处理

异常 是在程序执行期间出现的问题 当异常发生时&#xff0c;程序的正常流程被中断&#xff0c;应用程序将会异常终止 例1 执行上述代码出现以下错误 我们可以使用TRY和CATCH关键字的组合捕获异常 执行上述代码出现以下结果 例2 执行上述代码出现以下错误 我们可以使用TRY和CAT…

springboot+poi-tl根据模板导出word(含动态表格和图片),并将导出的文档压缩zip导出

springbootpoi-tl根据模板导出word&#xff08;含动态表格和图片&#xff09; 官网&#xff1a;http://deepoove.com/poi-tl/ 参考网站&#xff1a;https://blog.csdn.net/M625387195/article/details/124855854 pom导入的maven依赖 <dependency><groupId>com.dee…

Soft Robotics 变结构手掌和变刚度手指的仿人软体手的人机交互操作-武科大ESIR课题组师兄成果

一、引言 在当今的机器人技术领域&#xff0c;人类对机器人的需求日益增长&#xff0c;涉及到工业生产、医疗护理、服务业等各个领域。然而&#xff0c;由于任务的多样性和复杂性&#xff0c;单独依靠自主机器人操作往往难以满足实际需求。为了解决这一问题&#xff0c;人机协作…

白话微机:9.解释SoC和Linux

一. 前言&#xff08;回顾世界观&#xff09; 在“微机世界”&#xff0c;普通的城市(单片机)里&#xff0c;人又有一个别的名字叫做“数据”&#xff0c;人有0有1&#xff1b;人们也有住房&#xff0c;这些住房在这个世界叫做“存储器”&#xff1b;地上有路&#xff0c;这些路…

鸿蒙开发实战:【音频组件】

简介 音频组件用于实现音频相关的功能&#xff0c;包括音频播放&#xff0c;录制&#xff0c;音量管理和设备管理。 图 1 音频组件架构图 基本概念 采样 采样是指将连续时域上的模拟信号按照一定的时间间隔采样&#xff0c;获取到离散时域上离散信号的过程。 采样率 采样…

数据仓库的设计开发应用(一)

目录 一、数据仓库设计的特点二、数据仓库系统开发过程三、数据仓库系统的规划 一、数据仓库设计的特点 1、“数据驱动” 的设计 数据仓库是从已有数据出发的设计方法&#xff0c;即从数据源抽取数据&#xff0c;经转换形成面向主题&#xff0c;支持决策的数据集合。 以全面了…

MapReduce的原理分析

1.概述 MapReduce的思想核心是“分而治之,先分再合”&#xff0c;适用于大量复杂任务处理场景(大规模数据处理场景)。 MapReduce分两个阶段: map阶段(分)&#xff1a;如果任何可以拆分并且没有依赖&#xff0c;那么就把复杂的任务拆分成小任务&#xff0c;拆分成小任务之后&a…

【云原生-kubernetes系列】--kubernetes日志收集

1、ELK架构 1.1、部署ES集群 https://mirrors.tuna.tsinghua.edu.cn/elasticstack/apt/7.x/pool/main/e/elasticsearch/ 1、下载软件包 rootes-server1:~# wget https://mirrors.tuna.tsinghua.edu.cn/elasticstack/apt/7.x/pool/main/e/elasticsearch/elasticsearch-7.12.0-…

QMI8658芯片I2C驱动开发指南

这个芯片纯国产挺好用的&#xff0c;电路很好设计&#xff0c;我这垃圾焊功&#xff0c;纯手焊&#xff0c;&#xff0c;居然能用。 第一部分 硬件连接 画的很简陋&#xff0c;看看就可以了&#xff0c;这里I2C总线需要接10K上拉没有画出来&#xff0c;这个需要注意一下。 …

【XR806开发板试用】基于WEBSOCKET实现人机交互(控制开关灯)以及开发问题记录

一、开发板编译、功能介绍 根据官方文档编译烧录成功后&#xff0c;我们修改下官方例子&#xff0c;进行开发来实现websocket。 整体流程&#xff1a;开发板先自动寻找指定的wifi并且连接&#xff0c;连接成功后&#xff0c;通过websocket来与服务端连接&#xff0c;连接成功后…