磨人的KMP算法

之所以说KMP磨人是因为,他真的不怎么好懂,就算懂了,也不怎么好写0.0也有可能是我太菜了

KMP算法就是为了应对暴力匹配字符串带来的庞大的消耗,总的来说就是在匹配字符串的过程中如果发生匹配失败,不采用暴力匹配的方法直接从当前字符串的下一个位置开始匹配,而是最大程度的把匹配串向右移动尽可能多的字符。当然这里的移动并不是随便移动,而是根据一个移动表格(next数组)来进行移动

暴力匹配的思想就是逐个匹配,但是这是KMP怎么会这么low,当然对于下面这个字符串,刚开始可能和暴力匹配差不多

BBC ABCDAB ABCDABCDABDE

ABCDABD

依旧不相等,继续整体后移

BBC ABCDAB ABCDABCDABDE

#ABCDABD

整体移动到下面位置时,匹配成功一个字符

BBC ABCDAB ABCDABCDABDE

### ABCDABD

然后匹配一次对后面的字符进行匹配

BBC ABCDAB ABCDABCDABDE

### ABCDABD

到这个位置匹配失败,按照暴力匹配的方法应该将匹配串的头和目标串的第6个字符进行比较,但是根据KMP的思想,应该在出现错误的基础上,最大限度的右移匹配串

BBC ABCDAB ABCDABCDABDE

### ABCDABD

然后根据之前构造好的Next表(后续会说明Next表的原理),在D位置匹配失败,然后匹配成功的最后一个字符是B,B对应的Next数组值为2,这个时候我们就应该将字符串后移:(已经匹配的字符个数-部分匹配值)个字符

ABCDABD

000012

因为已经匹配的字符数是6,部分匹配值是2,所以得出字符串向后移动4个单位

BBC ABCDAB ABCDABCDABDE

### ####ABCDABD

然后按照常规的匹配的规则继续匹配,直到出现下图的情况。再按照KMP的处理方法,尽可能的后移匹配串,知道匹配成

BBC ABCDAB ABCDABCDABDE

### ####ABCDABD

到这里都好懂,然后就开始想这个Next数组是怎么求出来的?然后我就懵逼在Next数组上

说到这了都,问题就演变成了如何求Next数组的部分匹配值了。网上其他的博客上还引入了前缀和后缀的概念,但是我认为没有什么必要。所谓的部分匹配值就是,从头开始对匹配串进行重复查找,简单的来说A B C D A B D,1-4的部分匹配值为0,但是5-6出现了重复组A B,第7位虽然也在前面出现,但是组A B D没有在前面出现,所以D位置的部分匹配值为0

OK,原理大概就是这样,剩下的一个问题就是代码了

其实整体很难解决的就是一个Next数组的构造和KMP的主程序

根据上面的原理实际上Next数组就很好实现了

既然有了Next数组,那就可以很愉快的写KMP函数了

这么看的话磨人的KMP算法其实也不是很难

About the author

NOBUG.IN

Add comment

By NOBUG.IN

Your sidebar area is currently empty. Hurry up and add some widgets.