一幅图让你彻底理解KMP算法

KMP算法最难理解的莫过于next数组。为什么在p[j]!=p[k]时,需要将k赋值为next[k]?通过一副图分析了KMP算法中next数组的计算原理,指出next[k]表示的就是字符串长度为k的头部字符串的最长前缀和后缀,所以当p[j]!=p[k]时,应该将最长匹配长度k回退到next[k]的长度,然后开始新一轮的匹配过程!.

​​​对于KMP算法,最难理解的莫过于next数组是如何计算得到的。看了这幅图,你还不了解为什么吗?

假设当前考虑的是下标为j的字符,此时已经有头部k长度的字符尾部k长度的字符是相等的,即图中标的两个长度为k的子字符串(为什么?这难道不就是next数据的含义吗?)。

如下图,如果p[j]=p[k],万事大吉,说明头部字符尾部字符的长度都可以增加1。 KMP最难理解的是,如果p[j] != p[k]时,为什么要将k赋值为next[k] ??? 重点来了,你看下图中的那个头部长度为k的子字符串,他其实也是经过了前缀、后缀匹配过程的呢! 所以,对于长度为k的头部子字符串,他可能有图中蓝色部分的前缀和后缀。

本文来自微博视频下载工具

注意,如果图中头部的黄色表示的字符与下标j表示的字符相等,那么,下标j找到了他的最长前缀了。那头部黄色表示的字符的下标是多少????这就是关键!!头部黄色表示的字符的下标就是next[k]。 为什么?因为next[k]表示的就是字符串长度为k的头部字符串的最长前缀和后缀。这就是kmp算法中next数组的定义啊!

kmp算法next数组