KMP算法之next数组求解（代码）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了KMP算法之next数组求解（代码），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1698字，纯文字阅读大概需要3分钟。

内容图文

写在前面

考408期间学习的时候看到的bilibili的视频先附上：
链接: link
这个视频主要应付考试，没有讲代码的思路，这里我就顺着这个视频的思路，写出代码，思路如有不清晰之处，望指出，并且可以看看这个视频。

思路

以此为例：

观察我们可以知道先求出maxL，maxL是以当前字符结尾的匹配串。

计算方法：

第一个默认为0，第二个如果和第一个相同为1，不同为0（这里的b和a不同因此为0）。
往后的序列，可以按照以下方法计算：(由于string默认从0开始，因此上面的序号在代码中也是从0开始而不是从1开始)
由于前面的字符一定是以前面的字符为结尾的匹配字串，因此如果当前字符可以与前面一个字符匹配的字符下一个相同，则maxL[i]=maxL[i-1]+1；也就是上一个数得到next数组的+1。
如果不相同，就看当前字符与第一个字符相同不相同，相同则当前字符作为字串的开头，即为1，如果不同则为0；

如果上面看不懂就直接看例子：

如4号为的a，他的前面是3号位的a，maxL[3]=1，找到1号位的下一位2号位，是b，由于a和b不同。则判断a和字符串开头是否相同，因为都相同所以为1。
求出来maxL以后，左侧添加-1，向右平移再逐项+1（由于开头本来就是0，因此next[0]=maxL[0]这里不需要动）剩下的一个循环解决：

for(int i =s.length()-1;i>0;i--){
		next[i]=next[i-1]+1;
	}

代码

当然你如果觉得我的代码写的贼丑，自己改改就好了

#include<stdio.h>
#include<string>
#include<iostream>
using namespace std;
int next[100];
void getnext(string s){
	next[0]=0;
	for(int i =1;i<s.length();i++){
		if(i==1){
			if (s[1]==s[0]) next[1]=1;
			else next[1]=0;
		}
		if(s[i]==s[next[i-1]]) next[i]=next[i-1]+1;
		else if (s[i]==s[0]) {
			next[i]=1;
		}
		else{
			next[i]=0;
		} 
	}
	for(int i =s.length()-1;i>0;i--){
		next[i]=next[i-1]+1;
	}
}
int main(){
	string s;
	cin>>s;
	getnext(s);
	for(int i =0;i<s.length();i++)
	printf("%d ",next[i]);
	
}

运行结果图

视频中的例子：

王道数据结构kmp的题6：

均正确

• 点赞
• 收藏
• 分享
• • 文章举报

linazang 发布了12 篇原创文章 · 获赞 3 · 访问量 1288 私信 关注

内容总结

以上是互联网集市为您收集整理的KMP算法之next数组求解（代码）全部内容，希望文章能够帮你解决KMP算法之next数组求解（代码）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---