k@M0me’s Humble Abode      博  客   时 间 线   归  档 



KMP算法详解
Published on Fri May 08 2020 11:00:00 GMT+0000

KMP理论概要

KMP字符串匹配算法是一种效率更高的字符串匹配算法。相比于传统算法,由于其主串指针不需要回溯,因此大大减少了匹配需要的时间。

首先,让我们看看其是如何减少重复的步骤的:

假如有一字符串S:

1 2 3 4 5 6 7 8
a a b c a a b a

我们想要让字符串“aaba”与其匹配。

那么,匹配看起来就是这样:

第一次匹配:

1 2 3 4 5 6 7 8
a a b c a a b a
a a b a(不匹配)

此时指针回退,主串指针回退至2,模式串回退至1。

第二次匹配:

1 2 3 4 5 6 7 8
a a b c a a b a
a a(不匹配)

此时主串指针再次回退。

可以看出,我们的主串指针在匹配过程中一直在重复读取某一段内容,这是大大有损效率的。若是能使主串指针不回退,只控制模式串指针回退一段距离,这也许可以改善。

实际上,第二次匹配可以简化为:

1 2 3 4 5 6 7 8
a a b c a a b a
a(不匹配)

然后是第三次匹配:

1 2 3 4 5 6 7 8
a a b c a a b a
a a b a(匹配成功)

那么,如何算出模式串指针应当回退多少呢?

根据KMP算法的核心思想,模式串T拥有一个对应表,用于记录模式串T重复的部分。

观察以下两个对应表:

1 2 3 4 5 6 7 8
a a b a a a b a
0 1 2 1 2 3 3 4
1 2 3 4 5 6 7 8
a b c d e f g h
0 1 1 1 1 1 1 1

可以看出,1号表格中,在匹配到第8个位置时,若是不匹配,只需要回到4对应的位置继续匹配就可以了,但是2号表格中,每一次匹配都必须要回到位置1重新匹配。

原因在于此:

1 2 3 4 5 6 7 8
a a b a a a b a
0 1 2 1 2 3 3 4

可以看到,若是第8个字符不匹配并不影响前3个字符已经匹配成功的事实。因为5、6、7三个字符与1、2、3无异。既然我们已经匹配过a、b、c三个字符了,何必再匹配一次?

举例说明:

匹配 “aabaaaabcaabaaaba”与“aabaaaba”

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
a a b a a a b c a a b a a a b a
a a b a a a b a(不匹配)
与5相同 与6相同 与7相同 匹配 匹配 匹配
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
a a b a a a b c a a b a a a b a
a a b a(继续匹配) a a b a

可以看到,由于我们已经在匹配5、6、7三个字符时确定a、a、b三个字符是匹配的,那么我们就不需要在匹配前三个字符上浪费时间了。

那么,我们已经知道了如何使用模式串的“特性数组”来减少匹配重复字符上的浪费,但是这个数组怎样计算出来呢?

综合来看,我们计算此数组的目的就在于减少重复匹配,那么此数组的最大目的就是找出在制定字母之前有多少重复部分。

如:aabaaaba

1 2 3 4 5 6 7 8
a a b a a a b a
0(因为每次匹配都是先使指针+1再匹配,若是第一个字符就不匹配,那么就使指针位置为0,匹配时从第一个开始匹配。) 1(无论有无重复都为1) 2(重复了a) 1(没有重复) 2(重复了a) 3(重复了aa) 3(重复了aa) 4(重复了aab)

由此,推导程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
std::vector<int> getNext(std::string in) {
std::vector<int> res(in.length() + 1);
int i = 1, j = 0;
res[1] = 0;
while (i < in.length()) {
if (j == 0 || in[j - 1] == in[i - 1]) {
i++;
j++;
res[i] = j;
} else
j = res[j];
}
return res;
}

KMP再优化:

我们已经看出KMP算法是如何减少重复匹配来减少匹配时间的。但是,是否有一种更优化的方法呢?

观察以下字符串: