字符串匹配之KMP详解🤙 KMP

发表于

「这是我参与11月更文挑战的第16天，活动详情查看：2021最后一次更文挑战」

KMP

- KMP算法的时间复杂度是O(m+n),主要优点是：主串不回溯

一.示例图

#二.经典例题

剖析上面的例题

1
arduino复制代码p作为模式串'aabaac'      s作为主串'aabaabaabaac'

1. 首先我们先求解next数组

2. 主串一直往前走，模式串进行比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
css复制代码①
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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
css复制代码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图中的
  • 匹配值整体向右一位，是不是很神奇！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%