朴素模式匹配算法与KMP算法（非重点）

2024-07-17 18:34:02
开发
20

一. 朴素模式匹配算法

$\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$

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$

4.1 优化分析

$\quad$

在这里插入图片描述

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

$\quad$
$\quad$
不是所有的next数组的值都可以被优化

$\quad$

在这里插入图片描述

$\quad$

4.2 手算nextval数组

$\quad$

在这里插入图片描述

原文地址:https://blog.csdn.net/qq_61866637/article/details/140465891 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1813522540438622208.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部