KMP是为了解决串的匹配问题。
一、基础知识
1、概念
1.串的匹配问题:就是在一个长的主串s中找到另一个的短的子串t。
2.目标串(主串\文本串):被匹配的母串,串s被称为目标串。
3.模式串(子串):进行匹配的子串,串t被称为模式串。
2、前后缀
前后缀不能是字符串本身。
4.前缀:不包含尾字符的前面字符串的所有子串(需要挨个从左边取到右边)。
5.后缀:不包含首字符的前面字符串的所有子串(需要挨个从右边取到左边)。
6.相等前后缀:(前后缀相等认为可以进行跳步)
子串中它的前缀和后缀相等。它的这两前后缀就互称相等前后缀。
7.相等前后缀长度:就是相等前后缀的字符串的长度。
8.最长相等(公共)前后缀:能够进行跳步的最大
3、前缀表(部分匹配表)
定义是:在j处不匹配,找到j前面子串的后缀,找到与这个后缀相等的 前缀的后面重新开始匹配。
9.next数组(前缀表):当主串与模式串的某一位字符不匹配时,模式串(子串)要回退的位置。
10.next[j]:其值 = 第j位字符前面j-1位字符组成的子串的最长相等前后缀字符数的长度
4、暴力搜索:
两层for循环,一层for遍历文本串(主串),第二次for循环遍历模式串(子串),然后挨个去匹配。时间复杂度为O(m*n)。
二、算法原理
KPM算法原理:找到可以跳的步数(跳过已经匹配的部分开始匹配)。
①研究模式串(子串)的结构看哪里可以跳。②怎么进行跳。
关键步骤:找下一次能匹配(跳过去)的最长的缀,也就是最长公共前后缀。也就是在目标串s在相当于原字符串(主串)中的后缀和模式串(子串)t中的原字符串的前缀,求最长的公共前后缀。
总结:公共前后缀越多越长,能够跳的步骤就越多。如果模式串公共前后缀都为零,则KMP算法与暴力搜索算法是一样的。
三、实例
主串:aabaabaaf
子串:aabaaf
(1)构建next数组(前缀表)
next数组本质:寻找子串中“相同前后缀的长度 ”,且一定是最长的前后缀。
1)找出子串的最长相同前后缀的长度。
子串 | 前缀表(next数组) |
---|---|
a | 0 |
aa | 1 |
aab | 0 |
aaba | 1 |
aabaa | 2 |
aabaaf | 0 |
2)构建前缀表
索引下标 | 子串(模式串) | 前缀表 |
---|---|---|
0 | a | 0 |
1 | a | 1 |
2 | b | 0 |
3 | a | 1 |
4 | a | 2 |
5 | f | 0 |
(2)进行匹配:
1)进行第一次匹配。在第四个a后面我们找到了冲突的位置,b与f不匹配了,冲突了。
2)我们要找它的前面这个子串,aabaa的子串的最长相等前后缀是多少。
最长相等前后缀记录在前缀表中。此处的最长相等前后缀长度是2。
这个2意味着子串有这着一个后缀aa,前面也有一个与其相等的前缀aa。
我们在这个后缀的后面,不匹配了,冲突了,我们就要找与其相等的前缀 的后面,继续开始匹配。
3)与其相等的前缀 的后面下标就是这个字符串aabaa它的最最长相等前后缀的长度。
就是我们要继续去匹配的位置。 跳到下标2的位置继续匹配。
因为索引是0开始的我们跳到了下标为2的位置继续匹配。
4)进行第二次匹配
找到了aabaaf。用前缀表完成了匹配的过程。