# KMP详解

**Published by:** [ff](https://paragraph.com/@ff-4/)
**Published on:** 2022-02-08
**URL:** https://paragraph.com/@ff-4/kmp

## Content

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 a 'c' 此时第六位不匹配，那么我们看到第五位'a'匹配值是'2',已经匹配的是'5'所以使用公式 '5-2=3' 此时我们将模式串向后移动三位得到② ② a a b a a b a a b a a c a a b a a'c' 同理与上面思路相同，仍然是'5-2=3' 将模式串向后移动三位得到③ ③ a a b a a b a a b a a c a a b a a c 彩蛋到这里，大家重看图1，我们要求看的next其实就是将图1的图匹配值整体向右一位，不是很神奇！

## Publication Information

- [ff](https://paragraph.com/@ff-4/): Publication homepage
- [All Posts](https://paragraph.com/@ff-4/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@ff-4): Subscribe to updates