参考课程：宋会英老师——KMP算法——效率较高的匹配算法
D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法

纲要

• BF算法
• KMP算法
• 失败函数（next）的定义
• 算法的特点
• 改进NEXT值
• 代码实现
  在KMP算法的比较过程中，不产生回溯，匹配失败时，主串的指针不回溯，只要是在模式串中找到合适的字符（由失败函数确定）与其比较即可，故算法的渐进时间复杂度为O(n)。

KMP算法

传统的模式匹配算法（BF算法）

思想：

将目标串的第一个字符与模式串的第一个字符比较，若相等继续比较后续的字符。若不等，从第目标串的第二个字符重新和模式串的第一个字符比较。
以此类推直到模式串对应的字串。

代码实现：

int BFindex(string t,string p){
    if(t.length()<1||p.length()<1){
        return -1;
    }
    int i = 0; 
    int j = 0;
    while(i<t.length()&&j<p.length()){
        if(t[i] == p[j]){
            i++;
            j++;
        }else{
            i = i - j + 1;//i回溯 
            j = 0;  
        }
    }
    if(j>=p.length()){
        return i-p.length();
    }
    return 0;
    
}

复杂度分析：

每次匹配失败需要回溯，需要大量的重复匹配，复杂度为O(n*m)。

回溯的问题

（图片来源:严蔚敏数据结构11教程）
首先我们引入，需要了解后缀与前缀的概念（之后会有解释），当模式串和目标串匹配时，如果第一个元素不同，自然没有回溯问题，i会移动到下一个字符，当匹配到的字符数大于1的时候，一旦匹配失败，j需要回到0，而i需要回到匹配刚开始的下个位置进行重新匹配。如下图，当匹配很长一串都相同的时候，还需要回溯到第2个位置。

那么这个回溯是否必要呢？，在重新匹配的过程中，其实很多次匹配我们已经能确定无法匹配。经过分析，我们发现只有当完成匹配的模式串的字串真后缀和真前缀相同时，从后缀开始的地方进行匹配才有可能匹配成功（认真分析一下滑动模式串匹配的过程，就能发现只有真前缀和真后缀相同，从后缀开始的地方才有可能匹配，否则在模式串已匹配部分与目标串就不匹配了），如果不相等，之前的匹配都是多余的。那么既然i之前的位置可以确定匹配状态，那么i自然不需要回溯了，只需要让模式串的某个位置j开始继续匹配i就行了（下见KMP算法）

KMP匹配算法

算法的基本思想

KMP算法最大的改进之处，在匹配失败时，主串中的指针 i 不需要回溯，而是在模式中找到适当的字符继续比较。

KMP算法的过程

在分析kmp算法之前，看看kmp匹配的过程。

当匹配失败时，找到一个Pk与ti进行比较。如何找到这个Pk就是KMP算法的关键。

KMP算法关键( k需要满足的条件)

进一步分析，如果匹配到不等于，那么一定能得到的是，与t串对应的字符一定是相等的（只有相等才能匹配到i，j位置）。如下图：

k值是什么？

对于k值是什么，在之前回溯的问题的分析已经有提到了，k值自然就是真前缀的分割点或者是长度。（简单分析可知，一定要得到的是最长真前缀，这里不做分析）。

如何得到k值——失败函数(next)

在很多博客中没有提到失败函数这个词，在看的时候云里雾里，不明白这个next到底是什么。在宋会英老师的课程中，提到的这个词，有种豁然开朗的感觉。

现在我们知道，当我们匹配失败的时候不需要回溯i，那么匹配失当j位置匹配失败的时候（为什么是j不是i，因为k只与模式串有关），就对应了一个唯一k值。形成一一映射的关系。

• j位置的失败函数，需要看的是1~j-1序列

• 所以有两个固定的值 j=0时，k=-1;j=1时，k=0；
  

  由上我们可以给出定义：

利用失败函数进行匹配处理

• 例子：

  
  

KMP算法特点

• 效率高
• 不回溯
• 对目标串只需要扫描一遍（边读边匹配）。

对NEXT的改进

我们看一个为改进NEXT的KMP匹配的例子

代码实现

void getNEXT(){
    int k,j;
    k = -1;j = 0;NEXT[0] = -1;
    while(j<plen){
        if(k==-1||P[k] == P[j]){
            NEXT[++j] = ++k; 
            if(P[j] == P[k]){
                NEXT[j] = NEXT[k];
            }
        }else{
            k=NEXT[k];
        }
    }
    
}



int KMP_Count(){
    int ans = 0;
    int i = 0;
    int j = 0;
        getNEXT();
    while(i<tlen){
        if(j==-1||T[i] == P[j]){
            i++;
            j++;
        }else
        {
            j = NEXT[j];
        }
        if(j == plen){
            ans ++;
            j = NEXT[j];
        }
    }
    return ans;
}


int KMP_Index()
{
    int i = 0, j = 0;
    getNEXT();

    while(i < tlen && j < plen)
    {
        if(j == -1 || T[i] == P[j])
        {
            i++; j++;
        }
        else
            j = NEXT[j];
    }
    if(j == plen)
        return i - plen;
    else
        return -1;
}

• 参考了kuangbin的模板，在基础上改进了next（原模板的count方法就需要修改了）。