一、KMP算法的作用查询复杂度是O(nm)其中n是主字符串长度m是匹配串的长度。二、字符串的前缀和后缀(一)前缀指的是字符串从第1个字符串开始每次截取连续字符串的操作。例如字符串ABC的前缀有下列情况A、AB、ABC。(二)后缀指的是从第1个字符开始每次截取连续字符串到最后1个字符的操作。例如字符串ABC的后缀有下列情况ABC、BC、C。三、匹配串的前缀和后缀相同简单的说就是把前缀和后缀拿来比较有相同的就记录前缀或者后缀的长度。案例(避免选择整个字符串为前缀和后缀)以匹配串ABAB 为例比较1个字符前缀A和后缀B不相同。比较2个字符前缀AB和后缀AB相同记录前缀长度是2个字符。比较3个字符前缀ABA和后缀BAB不相同。四、KMP比较的思路(一)预处理求得匹配串每个字符前面的前缀和后缀相同的最长长度。默认值是0也就是从匹配串的第1个字符开始比较。(二)按顺序从第1个位置比较主串和匹配串的对应字符1、如果对应位置的字符相同去下一个位置比较。2、如果比较到匹配串的末尾代表匹配成功。3、如果对应字符不相等就把匹配串跳转到前缀后缀相同的长度继续比较。总之前面有比较过并且相同的就不需要从头开始比较了。