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

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

在这里插入图片描述

相关内容

热门资讯

红龙扑克辅助器!红龙扑克辅助器... 1、红龙扑克辅助器!红龙扑克辅助器(红龙扑克)好像存在有挂(详细辅助教程);详细教程。2、透视辅助简...
黑科技辅助挂!Wepoke一直... 黑科技辅助挂!Wepoke一直真的是有挂,Wepoke必胜都是真的有挂(详细计算辅助教程)1、ai机...
透视辅助!WpK透视辅助教程,... 透视辅助!WpK透视辅助教程,WPK透视本来是有挂(详细外卦挂教程)1、用户打开应用后不用登录就可以...
wepoke辅助机器人!wEP... wepoke辅助机器人!wEPOKE本来真的有挂,德州ai辅助神器wpk(详细透视辅助神器教程)1)...
德扑之星辅助器购买(德扑之星实... 德扑之星辅助器购买(德扑之星实战)辅助软件(辅助挂)一直是真的有挂(详细有作弊教程)1、起透看视 德...
黑科技透明挂!WEPoke辅助... 黑科技透明挂!WEPoke辅助工具,wepoke模拟器一贯有挂(详细ai代打教程)1、黑科技透明挂!...
透视辅助!红龙扑克辅助软件,红... 透视辅助!红龙扑克辅助软件,红龙扑克确实存在有挂(详细辅助教程)运辅助工具,进入游戏界面。进入辅助器...
wepoke有辅助挂!poke... wepoke有辅助挂!pokerworld真是存在有挂,wepower有外挂(详细ai代打辅助插件教...
aapoker透视辅助(aap... aapoker透视辅助(aapoker猫腻)aapoker 辅助工具(辅助挂)都是是有挂(详细辅助教...
透视辅助!AAPOKEr软件透... 透视辅助!AAPOKEr软件透明挂,aapoker有挂竟然是真的有挂(详细猫腻教程)1、aapoke...