KMP- KMP算法时间的复杂度是O(m+n)，主要优点是：主串不回溯一、示例图剖析的例子题p作为模式串'aabaac' s作为主串'aabaabaabaac' 1 . 首先我们先下课2 . 主串一直往前走，模式串进行比较① a a b a a b a a b a a c a a b a a 'c' 此时可以看到位于模式串的第'六位'字母c 与主串发生不匹配，这时去找next数组第六位，'next[6]=3' 那么此时回退到第三位根据公式'j=next[j]' ② a a b a a b a a b a a c a a b a a'c' 此时可以看到又是第六位字母'c'发生不匹配,仍然回退到'j=next[j]'-->相当于回退三位 ③ a a b a a b a a b a a c a a b a a c 此时终于 '全部匹配' 上面的例题的方法二1. 首先我们先将模式串的前后缀的部分匹配值求出，如'例1图' 2. 这时我们进行模拟匹配的时候，就可以使用公式 '右移位数 = 已匹配的字符数-对应的部分匹配值' ① a a b a a b a a b a a c a a b a ...