朴素模式匹配算法与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代打);所有人都在...
一分钟揭秘!微扑克辅助软件(透... 一分钟揭秘!微扑克辅助软件(透视辅助)确实是有挂(2024已更新)(哔哩哔哩);1、用户打开应用后不...
五分钟发现!广东雀神麻雀怎么赢... 五分钟发现!广东雀神麻雀怎么赢,朋朋棋牌都是是真的有挂,高科技教程(有挂方法)1、广东雀神麻雀怎么赢...
每日必看!人皇大厅吗(透明挂)... 每日必看!人皇大厅吗(透明挂)好像存在有挂(2026已更新)(哔哩哔哩);人皇大厅吗辅助器中分为三种...
重大科普!新华棋牌有挂吗(透视... 重大科普!新华棋牌有挂吗(透视)一直是有挂(2021已更新)(哔哩哔哩)1、完成新华棋牌有挂吗的残局...
二分钟内幕!微信小程序途游辅助... 二分钟内幕!微信小程序途游辅助器,掌中乐游戏中心其实存在有挂,微扑克教程(有挂规律)二分钟内幕!微信...
科技揭秘!jj斗地主系统控牌吗... 科技揭秘!jj斗地主系统控牌吗(透视)本来真的是有挂(2025已更新)(哔哩哔哩)1、科技揭秘!jj...
1分钟普及!哈灵麻将攻略小,微... 1分钟普及!哈灵麻将攻略小,微信小程序十三张好像存在有挂,规律教程(有挂技巧)哈灵麻将攻略小是一种具...
9分钟教程!科乐麻将有挂吗,传... 9分钟教程!科乐麻将有挂吗,传送屋高防版辅助(总是存在有挂)1、完成传送屋高防版辅助透视辅助安装,帮...
每日必看教程!兴动游戏辅助器下... 每日必看教程!兴动游戏辅助器下载(辅助)真是真的有挂(2025已更新)(哔哩哔哩)1、打开软件启动之...