KMP算法详解

什么是KMP算法

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

KMP算法的应用场景

• KMP算法是字符串查找的主流算法（也可以说是字符串匹配）

• 举个具体的例子：现在有主串“abcdabcdabe”和从串”abe“，现在要求在主串中找出从串的第一个匹配项的下标（下标从 0 开始），简单点来说，就是找到从串在主串第一次出现的位置。

KMP算法和暴力求解的比较

• 暴力求解的方法我已经在实现strStr中讲过，题目如图：
  
  
• 具体解析过程我们不再赘述，直接看暴力求解的代码：

int strStr(char * haystack, char * needle){
    int len_hay = strlen(haystack);
    int len_need = strlen(needle);
    if(len_need > len_hay)
        return -1;
    int i = 0,j = 0;
    int count_j = 0;
    while(1)
    {
        i = 0;  //每一次都要从字符串needle第一个字符开始匹配
        j = count_j;
        if(haystack[j] == '\0') //如果if条件为真，就说明haystack已经遍历完，且没有出现完全匹配的情况，返回-1
            return -1;
        //将字符串needle和字符串haystack的字符逐一匹配
        while(needle[i] == haystack[j] && needle[i] != '\0' && haystack[j]!= '\0')
        {
            i++;
            j++;
        }
        //如果循环退出后needle[i]为'\0'，就说明已经完全匹配，返回第一个匹配项的下标
        if(needle[i] == '\0')
            return count_j;
        //如果未完全匹配，则从haystack的下一个字符开始重新与字符串needle进行匹配
        else
            count_j++;
    }
    return -1;
}

• 可以发现，这种方法最坏的情况就是从串出现在主串的最后（如主串“abcdabe”，从串“abe”这种情况），因此暴力解法的时间复杂度为O(M * N)（M，N分别为主串和从串的长度）
  
• 而上面说到KMP算法可以将这一匹配过程的时间复杂度降为O(N + M)，极大地提高了效率。
  

字符串的前缀、后缀和最长相等前后缀

要理解KMP算法，首先要理解字符串前缀、后缀和最长公共前后缀这三个概念

• 字符串前缀：即是指不包含最后一个字符的所有以第一个字符开头的连续子串

• 如字符串“aebcdae”的前缀为{[a] , [ae] , [aeb] , [aebc] , [aebcd] , [aebcda]}，如图：
  
  

• 字符串后缀：即是指不包含第一个字符的所有以最后一个字符结尾的连续子串

• 如字符串“aebcdae”的前缀为{[e] , [ae] , [dae] , [cdae] , [bcdae] , [ebcdae]}
  
  

• 最长相等前后缀：即是前缀和后缀最长相等的连续子串

• 如字符串“aebcdae”的最长公共前后缀为[ae]

KMP算法实现字符串匹配的具体过程（图解）

我们以主串"abcababcabc"，从串 “abcabc”为例：

• 第一次匹配：在主串下标为5，从串下标为3时匹配失败，之后主串下标保持不变，从串下标变为为2
  
  
• 第二次匹配：在主串下标为5，从串下标为2处匹配失败，之后主串下标不变，从串下标变为0
  
  
• 第三次匹配：完全匹配
  
  
• 看完上面KMP算法具体的匹配过程，我们可以发现，当出现不匹配的情况时，我们的从串并没有返回到第一个字符重新开始匹配，而是返回到一个特定的位置，同样，主串是停留在原处（即不匹配的字符），而不是和暴力算法一样从第一个字符到第n个字符（遍历整个主串），那么，我们如何求出从串回溯的这一特定位置呢？
  

从串与主串的下标变化

首先我们规定从串进行匹配时，从串字符下标为j，主串字符下标为i

先下结论:当从串在下标为j的字符匹配失败时，要使匹配效率最高，j回退的位置就是 下标为从串j字符前子串的最长相等前后缀长度 的从串元素（j为下标）。而主串下标i保持不变。

j回退的位置(从串的下标变化)

• 就拿上面的例子来说:

• 在下标为5的字符（c）处匹配失败，我们将字符c前面的字符串称为子串
  
• 又由图我们可以发现，子串后面的两个元素已经和主串一一对应（匹配成功）
  

• 
  

• 而c前面子串"abcab"的最长公共前后缀为ab，其长度为2。
  
  
• 将后缀ab匹配主串ab调整为前缀ab对应主串ab.
  
• 即j回退到的字符就是下标为最长公相等前后缀长度的字符（即最长相等前后缀ab的后一个字符c）
  
  

主串的下标变化

• 为什么主串保持不变？

• 其实道理也是一样的：
  
• 主串下标为i前的两个字符已经和从串的前面两个字符一一对应（已经对从串的j进行了调整）
  
  
• 那么我们就只需要继续匹配从串后面的字符和主串字符，而不需要像暴力求解一样依次遍历主串元素，从而降低了时间复杂度。
  

• 特殊情况:

• 有细心的小伙伴可能会提出疑问:如果j已经回退到从串的第一个字符，但仍不能和主串匹配呢？
  
• 我们来看一个例子：主串"abdefac"，从串"ac"。

• 第一次匹配时，在i=1（字符b），j=1（字符c）时匹配失败
  
  
• 从串字符c前的子串为a，其最大相等前后缀长度为0，因此j回退到下标为0的字符a，i不变。
  
• 第二次匹配时，在i=1（字符b），j=0（字符a）时匹配失败
  
  
• 但此时j已经等于0了，已经退到不能再退了，这时我们就要移动i了，我们不断将i右移一个字符，直到主串下标为i的字符等于从串下标为j（j=0）的字符，然后再按上面的方法进行匹配。