KMP算法

对于长度分别为m与n的两字符串进行匹配的时间复杂度为O(m+n)的字符串匹配算法。

思想

设主串为 M，待匹配串为 N。初始位置为主串首字符。

[0]. 找到与N 匹配的最大前缀 X，若X=N，则结束并返回 X 的首字符下标；

[1]. 对 X，找出最长的相同前、后缀，设此后缀首字符下标为 x ；

[2]. 从主串下标 x 开始，重复 [0] ；

[3]. 若循环至主串末尾仍未结束，则结束并返回 无解。

图例