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 |
|
KMP再优化:
我们已经看出KMP算法是如何减少重复匹配来减少匹配时间的。但是,是否有一种更优化的方法呢?
观察以下字符串: