朴素模式匹配算法与KMP算法(非重点)
创始人
2025-01-09 02:30:40
0次

目录

  • 一. 朴素模式匹配算法
    • 1.1 什么是字符串的匹配模式
    • 1.2 朴素模式匹配算法
    • 1.3 通过数组下标实现朴素模式匹配算法
  • 二. KMP算法
    • 2.1 算法分析
    • 2.2 用代码实现(只会出现在选择题,考察代码的概率不大)
  • 三. 手算next数组
  • 四. KMP算法的进一步优化
    • 4.1 优化分析
    • 4.2 手算nextval数组

\quad

一. 朴素模式匹配算法

\quad

\quad

1.1 什么是字符串的匹配模式

\quad

在这里插入图片描述
\quad
在这里插入图片描述

\quad

1.2 朴素模式匹配算法

\quad
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

\quad

1.3 通过数组下标实现朴素模式匹配算法

\quad

在这里插入图片描述
在这里插入图片描述

鄙人所写

int Indexps(SString* a, SString* b) //朴素模式匹配算法 { 	int i = 1, j = 1; 	for (int k = 0; i < a->length - b->length + 1; k++) 	{ 		while(j<=b->length) 		{ 			if (a->ch[i] != b->ch[j]) 			{ 				break; 			} 			i++; 			j++; 		}  		if (j > b->length) 		{ 			return i - b->length; 		}  		i = i - j + 2; 		j = 1;   		if (i >= a->length - a->length + 2) 		{ 			return 0; 		}   	} } 

优化
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

\quad

二. KMP算法

\quad

\quad

2.1 算法分析

\quad

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
\quad
\quad
\quad
第二种情况
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
根据上面的经验,i不变,变的是j,而j是未知, 我们不妨先把j指向0
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

\quad

2.2 用代码实现(只会出现在选择题,考察代码的概率不大)

\quad
先不管next数组如何实现, 会手动算就行

在这里插入图片描述
在这里插入图片描述

\quad

三. 手算next数组

\quad

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

\quad
\quad

使用next数组进行模式匹配
在这里插入图片描述
在这里插入图片描述
练习题
在这里插入图片描述

\quad

四. KMP算法的进一步优化

\quad

\quad

4.1 优化分析

\quad

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

\quad
\quad
\quad
\quad
在这里插入图片描述
在这里插入图片描述
\quad
\quad
不是所有的next数组的值都可以被优化
在这里插入图片描述
\quad

在这里插入图片描述

\quad

4.2 手算nextval数组

\quad

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

相关内容

热门资讯

一分钟了解开挂!友空互娱开挂多... 一分钟了解开挂!友空互娱开挂多功能AI方法,友空互娱真是是有开挂方法1、友空互娱脚本辅助下载、友空互...
我来教大家透视挂!葫芦娃大厅透... 我来教大家透视挂!葫芦娃大厅透视挂多功能AIapp,葫芦娃大厅其实是真的有透视挂app1、超多福利:...
玩家必看科普开挂!福城娱乐开挂... 玩家必看科普开挂!福城娱乐开挂多功能AI插件,福城娱乐切实真的是有开挂插件1、打开软件启动之后找到中...
玩家必看科普外挂!海螺互娱外挂... 玩家必看科普外挂!海螺互娱外挂多功能AI方法,海螺互娱其实是真的有外挂方法1、实时海螺互娱透视辅助更...
盘点十款开挂!开心娱乐开挂多功... 盘点十款开挂!开心娱乐开挂多功能AI工具,开心娱乐一直真的有开挂工具1、盘点十款开挂!开心娱乐开挂多...
发现玩家外挂!神牛大厅外挂多功... 发现玩家外挂!神牛大厅外挂多功能AI软件,神牛大厅切实真的是有外挂软件1、玩家可以在神牛大厅透视最简...
技巧知识分享外挂!西兵外挂多功... 技巧知识分享外挂!西兵外挂多功能AI攻略,西兵果然真的是有外挂攻略西兵透视方法中分为三种模型:西兵靠...
实测交流作弊器!七天娱乐作弊器... 实测交流作弊器!七天娱乐作弊器多功能AIapp,七天娱乐总是真的有作弊器app进入游戏-大厅左侧-新...
一分钟揭秘外挂!欢盈娱乐外挂多... 一分钟揭秘外挂!欢盈娱乐外挂多功能AI软件,欢盈娱乐确实真的有外挂软件小薇(辅助器软件下载)致您一封...
科技通报透视挂!豪发娱乐透视挂... 科技通报透视挂!豪发娱乐透视挂多功能AI插件,豪发娱乐总是真的是有透视挂插件1、每一步都需要思考,不...