【算法思维】-- KMP算法

这篇具有很好参考价值的文章主要介绍了【算法思维】-- KMP算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

OJ须知:

  • 一般而言,OJ在1s内能接受的算法时间复杂度:10e8 ~ 10e9之间(中值5*10e8)。在竞赛中,一般认为计算机1秒能执行 5*10e8 次计算
时间复杂度 取值范围
o(log2n) 大的离谱
O(n) 10e8
O(nlog(n)) 10e6
O(nsqrt(n))) 10e5
O(n^2) 5000
O(n^3) 300
O(2^n) 25
O(3^n) 15
O(n!)

11

时间复杂度排序:o(1) < o(log2n) < o(n) < o(nlog2n) < o(n^2) < o(n^3) < o(2^n) < o(2^n) < o(3^n) < o(n!)


目录

字符串匹配算法

KMP算法

引出next数组

求next数组的练习

用手 + 看

用数学式

next数组的优化

引入nextval数组

复杂度分析


字符串匹配算法

        BF算法,即暴力(Brute Force)算法,是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T 的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和 T的第一个字符,依次比较下去,直到得出最后的匹配结果。BF算法是一种蛮力算法。(百度百科)

        接下来我们就将这段晦涩难懂的话,举一个例子:S:"ababcabcd",T:"abcd"。

  • 相等时:

【算法思维】-- KMP算法

  • 不相等时:

【算法思维】-- KMP算法

思路代码化展示: 

#include <cstdio>
#include <cassert>
#include <cstring>
int BF(const char* str, const char* sub)
{
	assert(str != nullptr && sub != nullptr);
	if (str == nullptr || sub == nullptr)
		return -1;
	int i = 0;
	int j = 0;
	int strLen = strlen(str);
	int subLen = strlen(sub);
	while (i < strLen && j < subLen)
	{
		if (str[i] == sub[j])
		{
			i++;
			j++;
		}
		else
		{
			//回退
			i = i - j + 1;
			j = 0;
		}
	}
	if (j >= subLen)
		return i - j;
	return -1;
}
int main()
{
	printf("%d\n", BF("ababcabcdabcde", "abcd"));
	printf("%d\n", BF("ababcabcdabcde", "abcde"));
	printf("%d\n", BF("ababcabcdabcde", "abcdef"));
	return 0;
}

KMP算法

        KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) [1]。(百度百科)

#区别:KMP 和 BF 唯一不一样的地方在,主串的 i 并不会回退,并且 j 也不会移动到 0 号位置。

  • 首先举例,为什么主串不回退? 

【算法思维】-- KMP算法

        如果按照BF算法,那么必须i变为第二个字符,将变为第一个字符。但是我们可以知道都比到这个位置了,那么从 i 向前 j 向前的字符串一定是相等的。

        而根据KMP算法就是,先分析短的子字符串。

【算法思维】-- KMP算法

        是不是有一对,以j - 1结尾的字符串和0开头的子字符串相等。而根据i 向前 j 向前的字符串一定是相等可以知道。

【算法思维】-- KMP算法

        看似是巧合,但这就是核心!因为此时我们并不需要将i移动,并且已经比较了一段。

【算法思维】-- KMP算法

        而现在的问题就是: 如何知道,它该移到哪一个指定的位置?

引出next数组

        KMP 的精髓就是 next 数组:也就是用 next[j] = k;来表示,不同的 j 来对应一个 K 值, 这个 K 就是你将来要移动的 j 要移动的位置。

而 K 的值是这样求的:

  1. 规则:找到匹配成功部分的两个相等的真子串(不包含本身),一个以下标 0 字符开始,另一个以 j-1 下标 字符结尾。
  2. 不管什么数据 next[0] = -1; next[1] = 0; 在这里,我们以下标来开始,而说到的第几个第几个是从 1 开始。

#一句话:next[0] = -1,next[1] = 0,此后找以0开头j - 1结尾的两字串相等的长度。

求next数组的练习

  • 用手 + 看

练习 1:对于 "ababcabcd",求其的 next 数组?

【算法思维】-- KMP算法

练习 2:对于 "abcabcabcabcdabcde",求其的 next 数组?

-1 0 0 0 1 2 3 4 5 6 7 8 9 0 1 2 3 0

#Tip:增加一定只会 +1

  • 用数学式

        到这里相信大家对如何求next数组应该问题不大了,那么接下来的问题就是:已知next[i] = k;怎么求next[i+1] = ?;

        首先假设:next[i] = k 成立,那么就有这个式子成立: P[0]...P[k-1] = P[x]...P[i-1]; 

【算法思维】-- KMP算法

        并且由于长度的相等,所以x也是可以推算而出的: k - 1 - 0 = i - 1 - x ,所以带入x: P[0]...P[k-1] = P[i-k]...P[i-1]; 

        到这一步:我们再假设如果 P[k] == P[i]; 我们可以得到 P[0]...P[k] = P[i-k]..P[i]; 那这个就是 next[i+1] = k+1; 

【算法思维】-- KMP算法

         再来看看: Pk != Pi 的时候。

【算法思维】-- KMP算法

融汇贯通的理解:(为什么以此方式回退?)


逻辑思维转换图

【算法思维】-- KMP算法

 #一句话:k一直回退,直到找到p[i] == p[k],否者k = -1,然后next[所求] = k + 1。

//KMP算法
#include <cstdio>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>

int KMP(std::string str, std::string sub)
{
	if (str.size() == 0 || sub.size() == 0)
		return -1;
	std::vector<int> next(sub.size(), 0);

	// 利用数学式求next
	next[0] = -1, next[1] = 0;
	for (int i = 1; i < sub.size() - 1; i++)
	{
		int k = next[i];
		while (sub[k] != sub[i])
		{
			k = next[k];
			if (k == -1) break;
		}
		next[i + 1] = k + 1;
	}

	int j = 0;
	int i = 0;
	while(i < str.size())
	{
        // j == -1 一开始就匹配失败了,那i++;j++;正好是sub重新开始,str下一个
		if (j == -1 || str[i] == sub[j])
		{
			i++;
			j++;
			if (j == sub.size()) return i - j;
		}
		else j = next[j];
	}
	return -1;
}
int main()
{
	printf("%d\n", KMP("ababcabcdabcdeebcd", "ebcd"));
	printf("%d\n", KMP("ababcabcdabcde", "abcde"));
	printf("%d\n", KMP("ababcabcdabcde", "abcdef"));
	return 0;
}

next数组的优化

        在上述的处理方式会出现下列情况。

【算法思维】-- KMP算法

        这一步一步回退不好,最好的就是一步就跳到第一个a,然后直接 -1 + 1 = 0,于是便有了next数组的优化,引入一个nextval数组。

引入nextval数组

nextval数组的求法:

  • 回退到的位置和当前字符一样,就写回退那个位置的nextval值。
  • 如果回退到的位置和当前字符不一样,就写当前字符原来的next值。

【算法思维】-- KMP算法

//KMP算法
#include <cstdio>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>

int KMP(std::string str, std::string sub)
{
	if (str.size() == 0 || sub.size() == 0)
		return -1;
	std::vector<int> next(sub.size(), 0);
	std::vector<int> nextval(sub.size(), 0);

	// 利用数学式求next
	next[0] = -1, next[1] = 0;
	nextval[0] = -1;
	for (int i = 1; i < sub.size() - 1; i++)
	{
		int k = next[i];

		// 求nextval
		if (sub[k] == str[i]) nextval[i] = nextval[i - 1];
		else nextval[i] = next[i];

		while (sub[k] != sub[i])
		{
			k = nextval[k];
			if (k == -1) break;
		}
		next[i + 1] = k + 1;
	}

	int j = 0;
	int i = 0;
	while(i < str.size())
	{
        // j == -1 一开始就匹配失败了,那i++;j++;正好是sub重新开始,str下一个
		if (j == -1 || str[i] == sub[j])
		{
			i++;
			j++;
			if (j == sub.size()) return i - j;
		}
		else j = next[j];
	}
	return -1;
}
int main()
{
	printf("%d\n", KMP("ababcabcdabcdeebcd", "ebcd"));
	printf("%d\n", KMP("ababcabcdabcde", "abcde"));
	printf("%d\n", KMP("ababcabcdabcde", "abcdef"));
	return 0;
}

利用nextval优化求next效果:

【算法思维】-- KMP算法文章来源地址https://www.toymoban.com/news/detail-457107.html

复杂度分析

  • 时间复杂度:O(m+n),srt字符串长m、sub字符串长n。
  • 空间复杂度:O(n)

到了这里,关于【算法思维】-- KMP算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图解KMP算法,带你彻底吃透KMP

    KMP算法 一直是一个比较难以理解的算法,本篇文章主要根据《大话数据结构》中关于KMP算法的讲解,结合自己的思考,对于KMP算法进行一个比较详细的解释。 由于博主本人水平有限,难免会出现一些错误。如果发现文章中存在错误敬请批评指正,感谢您的阅读。 字符串模式

    2024年02月08日
    浏览(55)
  • 时间复杂度:根号n一般来说大于log(n)

    f ( x ) = x − l o g 2 x f(x)=sqrt{x}-log_2 x f ( x ) = x ​ − l o g 2 ​ x 对这函数求导后,比较分母大小,可以得到结论 f ( x ) f(x) f ( x ) 先减后增,分界点为 x = 4 ( l n 2 ) 2 x = frac{4}{(ln2)^2} x = ( l n 2 ) 2 4 ​ f ( x ) f(x) f ( x ) 的图像如下所示: 两个函数的图像如下,只在 x = 4 , 16 x = 4,16

    2024年02月07日
    浏览(38)
  • 最详BF算法和KMP算法

      作者简介:大家好我是小唐同学(๑؂๑),为梦想而奋斗的小唐,让我们一起加油!!! 个人主页: 小唐同学(๑؂๑)的博客主页 博友们如果也是新手入门数据结构我希望大家可以多加练习 数据结构题库在牛客网就有已经给大家附上链接,可以直接点击跳转:刷题点这

    2023年04月09日
    浏览(48)
  • 【数据结构与算法】KMP算法

     在C语言的strstr的实现过程中,所涉及的算法较为简单,或者说只是一个简单的思路而已,在字符串过长时,所涉及的算法复杂度过大,那有没有比较简单的算法呢?这里就涉及到了KMP——由三位大佬提出的,下面我们一起来了解吧!  KMP算法是一种改进的字符串匹配算法

    2024年03月26日
    浏览(48)
  • 秒懂算法 | KMP算法(Java描述)

    Knuth-Morris-Pratt 算法(简称 KMP)是由高德纳(Donald Ervin Knuth)和沃恩·普拉特在1974年构思,同年詹姆斯·H·莫里斯也独立地设计出该算法,最终三人于1977年联合发表。该算法较Brute-Force算法有较大改进,主要是消除了目标串指针的回溯,从而使算法效率有了某种程度的提高。

    2024年02月07日
    浏览(37)
  • 图解KMP算法

    子串的定位操作通常称作串的模式匹配。 你可以理解为在一篇英语文章中查找某个单词是否存在,或者说在一个主串中寻找某子串是否存在。 假设我们要从下面的主串S = \\\"goodgoogle\\\" 中,找到T = \\\"google\\\" 这个子串的位置。利用朴素的模式匹配算法我们通常需要下面的步骤。 (1):

    2024年02月02日
    浏览(57)
  • 数据结构:KMP算法

         KMP算法是由Knuth、Morris和Pratt三位学者发明的,所以取了三位学者名字的首字母,叫作KMP算法。      KMP主要用于字符串匹配的问题,主要思想是 当出现字符串不匹配时,我们可以知道一部分之前已经匹配过的的文本内容,利用这些信息从而避免从头再开始匹配。    

    2024年02月04日
    浏览(48)
  • KMP算法(多种实现方式)

    利用已经匹配的数据,去除无效的从头匹配 首先我们找到 i=9,j=9时不匹配,如果时暴力算法,此时i应重新来到i=2的位置,j返回j=1的位置,开始新一轮的匹配 这样暴力匹配,就白白浪费了已经匹配的串,那么问题来了,我们应该如何利用已经匹配的串呢?? 我们看着图片,假设i返回i=2,j返回

    2024年02月08日
    浏览(43)
  • 数据结构--KMP算法

    模板: 例题:acwing--kmp字符串(831. KMP字符串 - AcWing题库) 给定一个字符串 S,以及一个模式串 P,所有字符串中只包含大小写英文字母以及阿拉伯数字。 模式串 P 在字符串 S 中多次作为子串出现。 求出模式串 P 在字符串 S 中所有出现的位置的起始下标。 输入格式 第一

    2024年02月11日
    浏览(42)
  • KMP算法的及其原理

     KMP算法 首先 我们先了解一下 KMP算法的作用 str1 和str2 字符串 如果str1中包含str2 那么返回头位置 如果不包含返回-1 首先 我们先加入一个概念: 有一个next数组 next[i]的值为 str2 中 以i-1位置为结尾的字符串中 最长相同前缀后缀为多长(相同前缀后缀 不是对称  aba 中

    2024年02月15日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包