模式匹配算法:KMP算法

模式匹配算法:KMP算法

图:北京航空航天大学

Guderian出品

模式匹配是数据结构中字符串的一种基本运算,给定一个字符串P,要求在某个字符串T中找出与字符串P相同的所有子串,这就是模式匹配。

模式匹配算法要解决的问题

  • detection :P是否出现
  • location :首次在哪里出现
  • counting :共有几次出现
  • enumeration :各出现在哪里

绪论

KMP算法(全称Knuth-Morris-Pratt算法)是一种高效的模式匹配算法。在模式匹配算法中,常见的算法包括BF算法朴素算法)、KMP算法BM算法RK算法有限自动机算法Horspool算法Sunday算法。在这些算法中,最经典的算法非KMP算法BM算法莫属。这两种算法都有一个共同点:抽象,理解难度大。实际上,KMP算法还有一个明显特点:会者不难。本文内容默认你已经明白BF算法的原理和不足(因此这部分内容将简单略过),展开讲述KMP算法的原理、优点和c++代码实现。相信你在学会KMP算法之后将会有一种“踏遍青山人未老,这边风景独好”的快意。让我们开始吧。

BF算法

BF算法的本质就是暴力搜索。既然要在串T中找出与串P相同的所有子串,那不妨找出串T中所有与串P长度相同的子串,在逐个判断这个子串是否与串P相同。具体的例子点击这里或者看下方的视频(讲得很形象了,应该不会有理解上的困难)。设strlen(T) == n, strlen(P) == m,则BF算法预处理时间为$0$,匹配时间为$O(mn)$,总时间复杂度为$O(mn)$(简直是蜗速),在大部分应用场景中并不优秀

KMP算法

更高的效率

容易看出BF算法的效率是十分蹩脚的,而它蹩脚的原因也很明显:在一次匹配尝试中,一旦失配(某一位匹配失败),就把串P整体向右移动一位。在模拟算法运行过程中,我们发现如果开始匹配时第一位就失配,那么只向右移动一位的确无可厚非,毕竟说不定移动一位之后就会匹配成功呢;但是如果已经匹配了串P的一部分了才失配,在向右移动一位之后,有时候(而且往往是经常)我们发现依然注定会匹配失败,也就是说在上次失败之后,向右移动一位再做尝试是根本不必要的,这种“只移动一位”的策略实际上造成了巨大的步骤浪费。那么有没有办法,把这些不必要的尝试舍弃,节约算法的运行时间呢?

此处我们需要考虑以下问题,以便对BF算法做出有效的改进:

  • 为什么有一些尝试是注定徒劳的?
  • 如何判断哪些尝试需要舍弃?
  • 如果不是向右移动一位,又应该如何确定向右移动的位数?

在看完点击这里(还是上面那个链接)之后,前两个问题都能得到答案。在链接的视频讲解中,讲述者构造了一个前缀表数组prefix table来确定串P中每个从头开始的子串的最长公共前后缀(自身除外,以下省略此说明),一旦失配,就把串P向右移动到失配位置左侧子串的最长前缀处,使它们重叠,也就是把下图中的1号移动到2号位置,继续从当前位置匹配,如果当前位置为串T的结尾,则结束匹配。

那么问题来了:为什么要把最长公共前缀移动至最长公共后缀的位置?这个移动距离能不能更短?能不能更长?

引理 串的最长公共前后缀最长公共前后缀是原串的次长公共前后缀

证明(逃

实际上,在BF算法的一次匹配过程中,一旦失配,就把串P整体向右移动一位再次尝试匹配。假设第一次匹配时在串P的第r + 1位失配,此时已经确定串P失配位置的前r项与串T相应位置元素匹配,也确定了串P失配位置的前r - 1项与串T相应位置元素匹配。那么第二次匹配成功,当且仅当在串P的前r项组成的子串中,前r - 1位字符组成的前缀和后r - 1位字符组成的后缀相同,即某一个公共前后缀长度为r - 1。也就是说,如果匹配失败向右移动s位,那么再次匹配成功的必要条件是串P在失配位置前的子串的某一个公共前后缀长度为r - s。如果串P在失配位置前的子串的最长公共前后缀长度就是r - s,匹配失败后向右移动了不足s位,这意味着移动距离过短,将会做一遍无用功。

如果移动距离过长,那就有可能会错过一个成功的匹配。如果匹配失败向右移动s位,那么再次匹配成功的必要条件是串P在失配位置前的子串的某一个公共前后缀长度为r - s。注意这里是必要条件而不是充分条件,在把串P向右移动的过程中,并不是在失配位置前随便放一个公共前后缀都能匹配成功,我们需要从最长公共前后缀开始尝试,逐步减少原失配位置前子串的长度,直到匹配成功或者串P在失配位置前子串最长公共前后缀长度变为0

此处我们引入next[]数组来记录在失配时应该把串P的哪一位移动到当前位置。对于串P的第j + 1位的字符来说,next[j + 1]的意义是由串P的前j项的子串中最长公共前后缀的长度。next[]数组是KMP算法降低时间复杂度的关键,在预处理时就已经确定。下面介绍next[]数组求法。

next数组求法

如果你直接跳过了前面看到了这里,那说明你已经看了无数多参考资料,还是搞不懂next[]数组求法的原理,几乎走投无路了。但是,正如B站鬼畜区某神所言:

我们遇到什么困难也不要怕,微笑着面对它!消除恐惧的最好办法就是面对恐惧!坚持就是胜利!加油!奥利给!

回到正题。

先考虑求next[]数组的朴素算法:我们要求一个长度为l的串S最长公共前后缀,因为自身除外,所以把串S复制一遍,产生一个串S',并让串S'的第1位对齐串S的第2位,尝试匹配剩余l - 1位。若匹配成功,则剩余l - 1位就是串P最长公共前后缀;若匹配失败,则把串S'向右移动1位,再次尝试,知道匹配成功或串S'已被移出串S的范围之内。

等一等,为什么这波操作如此熟悉?(战术后仰

是的,这就是所谓的“串P匹配自身”,有没有办法可以优化以上的朴素算法呢?

我们的任务是求出串P每一个由前j项元素组成的子串的最长公共前后缀的长度。假设串P从字符串下标1开始存储,规定next[1] = 0,并从第2位开始匹配。设用串P'匹配串P,当前匹配位置是串P'的第j + 1位,串P的第i位,如果失配,那么处理方法同上面介绍的一样,把串P'向右移动到失配位置左侧子串的最长前缀处,即令j = next[j](思想:回溯),使它们重叠,即把下图中的1号移动到2号位置,继续从当前位置匹配;如果第j + 1位匹配成功,则更新串Pi位元素组成的子串的最长公共前后缀的长度为j,即令next[i] = j

你已经明白了KMP算法的原理,那么不难推算出KMP算法的时间复杂度:预处理时间为$\Theta(m)$,匹配时间为$\Theta(n)$,总时间复杂度为$\Theta(m+n)$。与BF算法相比,KMP算法是一种优秀的模式匹配算法。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
KMP-MATCHER(T, P)

n = T.length
m = P.length

next = COMPUTE-PREFIX-FUNCTION(P)

j = 0
for i = 1 to n
while j > 0 and P[j + 1] != T[i]
j = next[j]
if P[j + 1] == T[j]
j = j + 1
if j == m
print "Pattern occurs with shift" i - m
j = next[j]

COMPUTE-PREFIX-FUNCTION(P)

m = P.length
let next[1..m] be a new array
next[1] = 0
j = 0
for i = 2 to m
while j > 0 and P[j + 1] != T[i]
j = next[j]
if P[j + 1] == T[j]
j = j + 1
next[i] = j
return next

例题:KMP算法模版

题目描述

输入两个字符串$s1$和$s2$(皆从下标为$1$处开始存储),$s2$为$s1$的子串,输出$s2$在$s1$中所有出现位置的下标。

输入格式

第一行为$s1$,第二行为$s2$

输出格式

每行一个正整数表示s2在s1中出现的位置

输入样例

1
2
123456123
123

输出样例

1
2
1
7

说明/提示

  • $s1$和$s2$的长度在$1000000$之内
  • 运行速度不能太慢

解题方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//Presented by G-SS-Hacker
//cc BY-NC-SA 4.0
//Run on C++

#include <iostream>
#include <cstring>

using namespace std;

const int MAXN = 1000000 + 100;
const int MAXM = 1000000 + 100;

//next,x0,x1,y0,y1,index cannot be named to variables
int nxt[MAXM]; //nxt[i]表示字串1到i最长公共前后缀的长度
int len1, len2;
char s1[MAXN], s2[MAXM];

void pre()
{
for(int j = 0, i = 2; i <= len2; i++)
{
while(j && s2[i] != s2[j + 1])
j = nxt[j];
if(s2[i] == s2[j + 1])
j++;
nxt[i] = j;
}
}

void kmp()
{
for(int j = 0, i = 1; i <= len1; i++)
{
while(j && s1[i] != s2[j + 1])
j = nxt[j];
if(s1[i] == s2[j + 1])
j++;
if(j == len2)
cout << i - len2 + 1 << endl, j = nxt[j];
}
}

int main()
{
cin >> s1 + 1 >> s2 + 1;

len1 = strlen(s1 + 1);
len2 = strlen(s2 + 1);

pre();
kmp();

return 0;
}

结束语

我们遇到什么困难也不要怕,微笑着面对它!消除恐惧的最好办法就是面对恐惧!坚持就是胜利!加油!奥利给!


【其他文章·数据结构】

本文标题:模式匹配算法:KMP算法

文章作者:G-SS-Hacker

发布时间:2019年11月26日 - 15:34:36

最后更新:2020年05月20日 - 09:50:00

原始链接:https://G-SS-Hacker.github.io/KMP算法/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。