数据结构4.3_字符串模式匹配——KMP算法详解

next数组表示字符串前后缀匹配的最大长度。是KMP算法的精髓所在。可以起到决定模式字符串右移多少长度以达到跳跃式匹配的高效模式。

以下是对next数组的解释:

数据结构4.3_字符串模式匹配——KMP算法详解

数据结构4.3_字符串模式匹配——KMP算法详解

如何求next数组:

相关链接:按顺序阅读为宜

详解KMP算法:https://www.cnblogs.com/yjiyjige/p/3263858.html       //我觉得算法部分,这篇讲得最好,优先看,例子很具体

字符串匹配KMP算法:https://kb.cnblogs.com/page/176818/            //例子很详细,第二个看;

KMP算法详解:https://blog.csdn.net/x__1998/article/details/79951598   //看完前两个后看这个效果好一些,为了编程方便,注意这里面把next数组由部分匹配表解释成了部分匹配表右移一位;

经典算法KMP:https://www.cnblogs.com/c-cloud/p/3224788.html          //写得精炼,需要前面看完后才可以看

KMP的next数组详解:https://blog.csdn.net/yutong5818/article/details/81319120   //例子很详细,但是后面有些啰嗦,容易绕进去。但是对next数组的本质解释得很清楚。next数组就是部分匹配表pmt

KMP算法next数组求法详解:https://blog.csdn.net/to_be_better/article/details/49086075   //也是关于求next数组的

上一篇:SSH agent 的使用 - 资料摘录


下一篇:算法进阶面试题01——KMP算法详解、输出含两次原子串的最短串、判断T1是否包含T2子树、Manacher算法详解、使字符串成为最短回文串