1. 程序员秋天
  2. 首页
  3. 算法入门教程（二）
  4. 正文

程序员的算法课（11）-KMP算法

分类：算法入门教程（二）    2024-03-25    阅读(52)

一、KMP算法定义

【百度百科】KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。

字符串的模式匹配是对字符串的基本操作之一，广泛应用于生物信息学、信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测等领域，如何简化其复杂性一直是算法研究中的经典问题。字符串的模式匹配实质上就是寻找模式串P是否在主串T 中，且其出现的位置。我们对字符串匹配的效率的要求越来越高， 应不断地改良模式匹配算法，减少其时间复杂度。

KMP算法是由D.E. Knuth、J.H.Morris和V.R. Pratt提出的，可在一个主文本字符串S内查找一个词W的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。这个算法是由高德纳和沃恩·普拉特在1974年构思，同年詹姆斯·H·莫里斯也独立地设计出该算法，最终由三人于1977年联合发表。该算法减少了BF算法中i回溯所进行的无谓操作，极大地提高了字符串匹配算法的效率。

二、算法说明

1.简单举例

设主串（下文中我们称作T）为：a b a c a a b a c a b a c a b a a b b

模式串（下文中我们称作W）为：a b a c a b

用暴力算法匹配字符串过程中，我们会把T[0] 跟 W[0] 匹配，如果相同则匹配下一个字符，直到出现不相同的情况，此时我们会丢弃前面的匹配信息，然后把T[1] 跟 W[0]匹配，循环进行，直到主串结束，或者出现匹配成功的情况。这种丢弃前面的匹配信息的方法，极大地降低了匹配效率。

而在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。

比如，在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的：在已经匹配的模式串子串中，找出最长的相同的前缀和后缀，然后移动使它们重叠。

在第一次匹配过程中

T:a b a c a a b a c a b a c a b a a b b

W:a b a c a b

在T[5]与W[5]出现了不匹配，而T[0]~T[4]是匹配的，其中T[0]~T[4]就是上文中说的已经匹配的模式串子串，移动找出最长的相同的前缀和后缀并使他们重叠：

T:a b a c aa b a c a b a c a b a a b b

W:a b a c a b

然后在从上次匹配失败的地方进行匹配，这样就减少了匹配次数，增加了效率。

然而，如果每次都要计算最长的相同的前缀反而会浪费时间，所以对于模式串来说，我们会提前计算出每个匹配失败的位置应该移动的距离，花费的时间就成了常数时间。

2.再说明：

  • 假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置

  • 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；

  • 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。

    • 换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值（next 数组的求解会在下文的3.3.3节中详细阐述），即移动的实际位数为：j - next[j]，且此值大于等于1。

很快，你也会意识到next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀。

此也意味着在某个字符失配时，该字符对应的next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置）。如果next [j] 等于0或-1，则跳到模式串的开头字符，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，而不是跳到开头，且具体跳过了k 个字符。

 

这时，最自然的反应是，将模式串整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。

 

一个基本事实是，当空格与D不匹配时，你其实是已经知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，而是继续把它向后移，这样就提高了效率。

怎么做到这一点呢？可以针对模式串，设置一个跳转数组int next[]，这个数组是怎么计算出来的，后面再介绍，这里只要会用就可以了。

i 0 1 2 3 4 5 6 7
模式串 A B C D A B D '\0'
next[i] -1 0 0 0 0 1 2 0

已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。根据跳转数组可知，不匹配处D的next值为2，因此接下来从模式串下标为2的位置开始匹配。

 

三、next数组是如何求出的

两个概念：前缀 和 后缀。

 

由上图所得， "前缀"指除了自身以外，一个字符串的全部头部组合；"后缀"指除了自身以外，一个字符串的全部尾部组合。

next数组的求解基于“前缀”和“后缀”，即next[i]等于P[0]...P[i - 1]最长的相同前后缀的长度。

i 0 1 2 3 4 5 6 7
模式串 A B C D A B D '\0'
next[ i ] -1 0 0 0 0 1 2 0

1、 i=0，对于模式串的首字符，我们统一为next[0]=-1；
2、 i=1，前面的字符串为A，其最长相同前后缀长度为0，即next[1]=0；
3、 i=2，前面的字符串为AB，其最长相同前后缀长度为0，即next[2]=0；
4、 i=3，前面的字符串为ABC，其最长相同前后缀长度为0，即next[3]=0；
5、 i=4，前面的字符串为ABCD，其最长相同前后缀长度为0，即next[4]=0；
6、 i=5，前面的字符串为ABCDA，其最长相同前后缀为A，即next[5]=1；
7、 i=6，前面的字符串为ABCDAB，其最长相同前后缀为AB，即next[6]=2；
8、 i=7，前面的字符串为ABCDABD，其最长相同前后缀长度为0，即next[7]=0；

为什么根据最长相同前后缀的长度就可以实现在不匹配情况下的跳转呢？举个代表性的例子：假如i = 6时不匹配，此时我们是知道其位置前的字符串为ABCDAB，仔细观察这个字符串，首尾都有一个AB，既然在i = 6处的D不匹配，而因为前6个字母都是匹配的，此时前后缀是AB，说明AB已经不用比了，我们可以直接把i = 2处的C拿过来继续比较，而这个AB就是ABCDAB的最长相同前后缀，其长度2正好是跳转的下标位置。

最长相同前后缀是关键。

四、 扩展1：BM算法

KMP的匹配是从模式串的开头开始匹配的，而1977年，德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了一种新的字符串匹配算法：Boyer-Moore算法，简称BM算法。该算法从模式串的尾部开始匹配，且拥有在最坏情况下O(N)的时间复杂度。在实践中，比KMP算法的实际效能高。

BM算法定义了两个规则：

  • 坏字符规则：当文本串中的某个字符跟模式串的某个字符不匹配时，我们称文本串中的这个失配字符为坏字符，此时模式串需要向右移动，移动的位数 = 坏字符在模式串中的位置 - 坏字符在模式串中最右出现的位置。此外，如果"坏字符"不包含在模式串之中，则最右出现位置为-1。
  • 好后缀规则：当字符失配时，后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串上一次出现的位置，且如果好后缀在模式串中没有再次出现，则为-1。

五、扩展2：Sunday算法

上文中，我们已经介绍了KMP算法和BM算法，这两个算法在最坏情况下均具有线性的查找时间。但实际上，KMP算法并不比最简单的c库函数strstr()快多少，而BM算法虽然通常比KMP算法快，但BM算法也还不是现有字符串查找算法中最快的算法，本文最后再介绍一种比BM算法更快的查找算法即Sunday算法。

Sunday算法由Daniel M.Sunday在1990年提出，它的思想跟BM算法很相似：

  • 只不过Sunday算法是从前往后匹配，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。

  • 如果该字符没有在模式串中出现则直接跳过，即移动位数 = 匹配串长度 + 1；

  • 否则，其移动位数 = 模式串中最右端的该字符到末尾的距离+1。

更详细的介绍请参考很详尽KMP算法（厉害）。

六、为什么JDK String为什么不使用KMP算法？

在JDK1.8中我点开了String的indexOf(String str)发现并没有使用KMP算法。那么为什么JDK不使用KMP算法呢？

1）大部分比较是短字符串，普通算法的O(nm)已经够用，而KMP算法在较短字符串里是O(n+m)。KMP算法的常数因子会拖慢算法。

2)因为是公共库函数，需要考虑各种情况的性能。可能你也不想突然的内存开销。

3）也许未来的JDK版本会像Hashmap里的红黑树一样增加特定情况的算法优化。

六、KMP核心代码

    private static int[] getNext(String pattern){

        int j = 0,k = -1;
        int[] next = new int[pattern.length()];
        next[0] = -1;
        while(j < pattern.length() - 1){
            if(k == -1 || pattern.charAt(j) == pattern.charAt(k)){
                j++;
                k++;
                //改进next数组
                if(pattern.charAt(j) != pattern.charAt(k)){
                    next[j] = k;
                }else{
                    next[j] = next[k];
                }
            }else{
                k = next[k];
            }
        }
        return next;
    }

    public static int indexOf(String target, String pattern){
        
        int i = 0,j = 0;
        
        int[] next = getNext(pattern);
        
        while(i < target.length()){
            
            if(j == -1 || target.charAt(i) == pattern.charAt(j)){
                
                i++;
                j++;
            }else{
                j = next[j];
            }
            if(j == pattern.length()){
                
                return i - j;
            }
        }
        return -1;
    }

分析：

k和j就像是两个”指针“，一前一后，通过移动它们来找到最长的相同前后缀。

七、一点小总结

1、 KMP算法在匹配过程中将维护一些信息来帮助跳过不必要的检测，这个信息就是KMP算法的重点--next数组（也叫fail数组，前缀数组）所以，这个next数组很关键；
2、 有了next数组，我们就可以通过next数组跳过不必要的检测，加快字符串匹配的速度；
3、 KMP算法的精髓在于对已知信息的充分利用，这体现在待匹配串的匹配上面，更用于预处理时自己匹配自己上面；
4、 每一趟匹配完成后，利用上一趟匹配的结果，将模式向右滑动尽可能远的一段距离；

我的微信公众号：架构真经（id：gentoo666），分享Java干货，高并发编程，热门技术教程，微服务及分布式技术，架构设计，区块链技术，人工智能，大数据，Java面试题，以及前沿热门资讯等。每日更新哦！

 

参考资料：

1、 https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html；
2、 https://baike.baidu.com/item/kmp%E7%AE%97%E6%B3%95/10951804?fr=aladdin；
3、 https://www.jianshu.com/p/ef5501c2c968；
4、 https://blog.csdn.net/leejuen/article/details/88689399；
5、 https://www.jianshu.com/p/0267b76368d1；
6、 https://blog.sengxian.com/algorithms/kmp；
7、 https://segmentfault.com/a/1190000008575379；

版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: