朴素模式匹配算法与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

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

在这里插入图片描述

相关内容

热门资讯

透视安装!wpk透视辅助下载(... 透视安装!wpk透视辅助下载(透视)作弊(真是存在有挂)在进入wpk透视辅助下载辅助挂后,参与本局比...
透视代打!wepoker破解是... 透视代打!wepoker破解是真的还是假的(透视)wepoker破解器激活码(好像是有挂)1、每一步...
透视模拟器!aapoker破解... 透视模拟器!aapoker破解侠是真的吗(透视)辅助插件工具(本来真的有挂)1、构建自己的aapok...
透视存在!wpk俱乐部是做什么... 透视存在!wpk俱乐部是做什么的(透视)透视是真的假的(其实真的是有挂);wpk俱乐部是做什么的辅助...
透视计算!aapoker辅助软... 透视计算!aapoker辅助软件合法吗(透视)万能辅助器(一直真的有挂)1、打开软件启动之后找到中间...
透视了解!wepoker怎么设... 透视了解!wepoker怎么设置房间(透视)wepoker辅助器下载(切实有挂)一、wepoker怎...
透视好友房!wpk真的有透视嘛... 透视好友房!wpk真的有透视嘛(透视)透视辅助下载(切实存在有挂);1、下载好wpk真的有透视嘛辅助...
透视辅助!aapoker真的假... 透视辅助!aapoker真的假的(透视)插件(果然是真的有挂)1、aapoker真的假的系统规律教程...
透视透视!wepoker透视脚... 透视透视!wepoker透视脚本是什么(透视)wepoker辅助器官方(好像有挂)wepoker透视...
透视能赢!wpk俱乐部怎么作弊... 透视能赢!wpk俱乐部怎么作弊(透视)辅助购买(确实真的是有挂)1、该软件可以轻松地帮助玩家将wpk...