Skip to content
This repository has been archived by the owner on Jan 7, 2023. It is now read-only.

DS_Doc_3_3_KMP算法

Jump to bottom
KimYang edited this page Oct 10, 2020 · 1 revision

KMP 算法

简单模式匹配的缺点

image-20200804224435660

改进思想

image-20200804224530991

情况一

image-20200804224626232

image-20200804224704994

image-20200804224731389

情况二

image-20200804224917143

情况三：

iShot2020-08-04下午10.51.24

4这里有可能多比较一次：因为4和6已经不等，但是1和6相同，这里仍会期待1和6相同，再进行一次比较，所以这里它并不是最优的算法，但是相比于朴素模式匹配，它还是少对比了两次

image-20200804225536657

同理j指向3时少对比1次

总结：

image-20200804230434402

具体代码实现

image-20200804230554660

求next数组

image-20200805131252851

image-20200805131431528

image-20200805131611443

代码实现求next数组

image-20200805131821691

回顾总结

image

Clone this wiki locally