KMP算法计算next代码理解
2021/10/21 14:10:55
本文主要是介绍KMP算法计算next代码理解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
KMP算法计算next代码理解
- 顺代码思路
- 要了解以下几个问题
- 1.为什么比较T[j]和T[k]就行了?
- 2.k要回溯到哪个位置?
这一篇主要讲计算next代码的理解,默认已经会手算next,如果不会先看看下面这一篇:
手算next的理解
要理解一段代码,最简单的就是跟着代码走一遍
顺代码思路
可以看出,j的作用相当于是遍历整个字符串,当长度为0、1、2… …
而k的作用则是计算相应长度下的next值。
比较T[j]与T[k],如果相等,j后移,k加一;否则,j不动,k回溯。、
要了解以下几个问题
接下来要了解以下几个问题:
1.为什么比较T[j]和T[k]就行了?
2.k要回溯到哪个位置?
1.为什么比较T[j]和T[k]就行了?
首先是第一个问题:为什么比较T[j]和T[k]。
以上图序号六那一段为例,比较的是T[3]与T[1],因为T[2]与T[0]在上一段就比较过了,并且相等,因此这里实际上相当于比较T[3]T[2]与T[1]T[0]是否相等,这一步其实对应next分段函数中的第二种情况。
这样就可以与手算代码相联系一下:
有没有稍微看明白一点?
2.k要回溯到哪个位置?
接下来是重头戏:第二个问题——k要回溯到哪个位置
以上面顺代码走的最后一步为例:
现在应该大概能理解这段代码了吧。
设计这个算法的人真是个天才!
这篇关于KMP算法计算next代码理解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)