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

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

在这里插入图片描述

相关内容

热门资讯

透视科技!hhpoker有辅助... 透视科技!hhpoker有辅助吗,一向真的是有挂(透视)玩家教你(有挂方法)1、首先打开hhpoke...
透视攻略"wepok... 透视攻略"wepoker辅助透视软件"确实是真的有挂(透视)2025新版(有挂揭秘)wepoker辅...
透视智能ai!aapoker透... 透视智能ai!aapoker透视插件(透视)透视软件(一直有挂)1、每一步都需要思考,不同水平的挑战...
透视科技!德普之星私人局辅助器... 透视科技!德普之星私人局辅助器,切实真的是有挂(透视)技巧教程(有挂工具)1、德普之星私人局辅助器a...
透视私人局!aapoker辅助... 透视私人局!aapoker辅助器怎么用(透视)万能辅助器(切实真的是有挂)1、让任何用户在无需aap...
透视黑科技"红龙po... 透视黑科技"红龙poker有辅助吗"都是真的有挂(透视)力荐教程(有挂工具)1、这是跨平台的红龙po...
透视规律!wpk辅助购买,果然... 透视规律!wpk辅助购买,果然是真的有挂(透视)安装教程(有挂解密)1、wpk辅助购买透视辅助简单,...
透视线上!aapoker怎么控... 透视线上!aapoker怎么控制牌(透视)插件(都是存在有挂)1、每一步都需要思考,不同水平的挑战会...
透视黑科技"竞技联盟... 透视黑科技"竞技联盟透视"确实有挂(透视)必赢方法(有挂教程);1、竞技联盟透视透视辅助简单,竞技联...
透视神器!约局吧游戏挂,总是是... 透视神器!约局吧游戏挂,总是是真的有挂(透视)透明挂教程(有挂细节);约局吧游戏挂软件透明挂微扑克w...