32KMP算法

KMP算法

字符串匹配，用于匹配字符串的下标

对正常单个字符依次匹配的优化。

在匹配失败时，主串指针不需要回溯，子串指针回溯。

方法

设定一个next数组，存储子串下标要回溯的位置。

假如next[j]表示，对子串前j-1个字符而言，前缀与后缀相同的字符串的最大长度+1；

由此给出next数组的每一个元素值，得到整个next数组。（没有前后缀的为0）