Java教程

2022.2.8学习总结

本文主要是介绍2022.2.8学习总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

上午学习了kmp算法的思想,下午学习了如何实现kmp算法,并对这些内容进行了总结。

写在前面

文章中可能会先讲解很多貌似毫不相关的知识点,但这些都是学习kmp算法需要知道的东西,先了解这些知识点后我们就可以更好的理解kmp算法了。

目录

kmp的作用

暴力算法简介

kmp算法相对于暴力算法的优化

前后缀

最长相等前后缀

获取前缀值

构建前缀表


kmp的作用

在一个已知字符串(文本串)中查找子串(模式串)的位置,也叫做串的模式匹配。

暴力算法简介

从主串s 和子串t 的第一个字符开始,将两字符串的字符一一比对,如果出现某个字符不匹配,主串回溯到第二个字符,子串回溯到第一个字符再进行一一比对......一直到子串字符全部匹配成功。

最好的时间复杂度:O(n)

最坏的时间复杂度:O(m*n)

kmp算法相对于暴力算法的优化

KMP 算法主要是通过消除主串指针的回溯,以及改变字串回溯的位置来提高匹配的效率的

具体实现就是通过一个next()函数(即构造的前缀表)实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)

前后缀

前缀表示包含第一个字符,但不包含最后一个字符的字串

后缀表示包含最后一个字符,但不包含第一个字符的字串

上例子:

字符串 abcdab
前缀的集合:{a,ab,abc,abcd,abcda}
后缀的集合:{b,ab,dab,cdab,bcdab}

最长相等前后缀

字符串 abcdab
前缀的集合:{a,ab,abc,abcd,abcda}
后缀的集合:{b,ab,dab,cdab,bcdab}
最长相等前后缀就是ab

理解了这里,关于kmp算法子串回溯到哪个字符,现在可以着手解决了

获取前缀值

事实上,每一个字符前的字符串都有最长相等前后缀,而且最长相等前后缀的长度是我们移位的关键,所以我们单独用一个next数组存储子串的最长相等前后缀的长度。

next数组即我们需要构造的前缀表

每一个字符前的字符串的最长相等前后缀即该字符的前缀值

前缀值:

前缀值不仅仅代表着对应位置字符串前后缀相同元素长度的最大值

因为是前后缀的公共元素,它还可以表示该位置与从字符串首位起固定位置的字符相同,即指向自身与其相同的元素的位置。

文本串用例:ABABD

前缀表(前缀值表)
在这里插入图片描述 

对于任意一个字符串,我们很容易得到它的第一个前缀字符(数组索引为0)对应的前缀值一定为0(因为第一个前缀字符只有一个字符A没有前后缀,所以也不存在公共元素)

构建前缀表

分为三步:
1、初始化
2、前后缀的末尾不相同时怎么处理(有的文章直接就写个前后缀,让你看的一头雾水)
3、前后缀的末尾相同时怎么处理

 

void kmp(next,s)
{
	j=0;
	next[0]=0;//初始化
	for(i=0;i<s.size();i++)
	{
		while(i>0&&s[i]!=s[j])
			j=next[i-1];//前后缀的末尾不相同时怎么处理
		if(s[i]==s[j]) j++;//前后缀的末尾相同时怎么处理
		next[i]=j;//更新 
	}
}

这篇关于2022.2.8学习总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!