KMP算法主要用于解决字符串的匹配问题。即给定两个字符串text与pattern,需要判断pattern是否是text的子串。

假设text的长度为n,pattern的长度为m,那么用暴力搜索的算法解决该问题需要的时间复杂度为O(m*n)。而KMP算法需要的时间复杂度仅为O(m+n)。Knuth、Morris、Pratt是发明这个算法的三位科学家。

KMP算法最浅显理解——一看就明白  https://blog.csdn.net/starstar1992/article/details/54913261

以下是算法笔记里对kmp的讲解

1.next 数组

1.1 next数组定义

  在学习KMP算法之前首先学习一下next数组。假设有一个字符串(下标从0开始)。next[i] 表示使该字符串的子串s[0···i]的前缀s[0···k]和后缀s[i-k···i]相等的最大k(k<i:前后缀可以重合不能为整个子串);如果找不到相等的前后缀组,那么next[i] = -1

  以字符串s = "ababaab"为例,其对应的next数组为[-1,-1,0,1,2,3,-1]。

  当i = 0: 子串为"a",找不到相等的前后缀(因为前后缀不能包含整个s[i]),因此next[0] = -1;

  当i = 1: 子串为"ab",找不到相等的前后缀,因此next = -1;

  当i = 2: 子串为"aba", k = 0时 "a" = "a"; k = 1时,"ab" != "ba";因此next[2] = 0;

  依次类推可得到整个next数组。

1.2 next数组的计算

  暴力求解next数组效率不高,下面介绍如何用“递推”的方式高效的求解next数组。即假设已经求出next[0]~next[i-1],使用它们的结果来快速得到next[i]。

  为方便讨论,假设已知next[0] = -1 ; next[1] = -1 ; next[2] = 0; next[3] = 1,现在来求解next[4]。当得到next[3] = 1时,最长相等的前后缀为"ab",之后在计算next[4]时,由于s[4] == s[next[3]+1],故可将"ab"拓展为“aba”,即next[4] = next[3] + 1 = 2。

  在此基础上计算next[5]。由于s[5] ! = s[next[4]+1],因此不能拓展。此时需要做的操作是缩短。希望能找到一个j,使得s[5] ==s[j+1]成立并满足s[0···j]是s[0···2]的一个后缀。同时为了满足相等的前后缀尽量长的目标,找到的j应该尽可能大。

  很显然,只需要令j = next[2](找到"aba"的k),判断其是否满足s[5] ==s[j+1]:如果成立,next[5] = j + 1;如果不成立,就不断让j = next[j],直到j回到-1,或是途中s[5] = = s[j+1]成立。在本例中,j = -1时满足条件,故next[5]=-1+1 = 0。

  上述过程总结为一般算法描述为:

    1. 初始化next数组,令j = next[0] = -1;
    2. 让i 在1~len-1范围遍历(len为字符串s的长度),对每个i,执行3,4,以求出next[i];
    3. 不断让j = next[j],直到j退回到-1,或是s[i] == s[j+1]成立;
    4. 如果s[i] == s[j+1],则next[j] = j+1;否则next[i] = j。

  代码实现如下:

//getNext 求解长度为len的字符串s的next数组
void getNext(char s[],int len){
    int j = -1;
    next[0] = -1;  //init
    for(int i = 1; i < len ; i++){   //求解next[1] ~ next[len - 1] 
        while(j != -1 && s[i] != s[j+1] ){
            j = next[j];
        }
        if(s[i] == s[j+1]){
            j++;     //j指向next[i] 
        }
        next[i] = j;        
    }
}

2.KMP算法

2.1 KMP算法实现字符串匹配

  设有text = "abababaabc",pattern = "ababaab",希望判断patten是否是text的子串。令i指向text的当前欲比位,令j指向patten中当前已被匹配的最后一位,这样只需要满足text[i]==pattern[j+1],就说明pattern[j+1]也被匹配成功,此时让i,j加1以继续比较;如果不满足text[i]==pattern[j+1],参见第一小节next数组的定义,只需令j = next[j],继续比较即可。在本例中,i指向text[4],j指向pattern[3],此时满足text[i] == pattern[j+1],故i,j加一继续匹配。当i指向text[5],j指向pattern[4]时不满足text[i] == pattern[j+1]匹配失败。令j = next[j] =2,此时满足匹配条件,故i,j均加一继续匹配。随后发现直至j==6均成功匹配,说明pattern是text的一个子串。

  下面给出算法描述与代码实现:

    1. 初始化j = -1,j表示pattern当前已被匹配到的最后位;
    2. 让i遍历文本串text,对每个i,执行3,4来试图匹配text[i]和pattern[j+1]l
    3. 不断令j = next[j],直到j回退到-1,或是text[i]=pattern[j+1]成立;
    4. 如果text[i] == pattern[j+1],则令j++。如果j达到m-1,说明pattern是text的子串,返回true。
//KMP算法  判断pattern是否是text的子串 
bool KMP(char text[],char pattern[]) {
    int n = strlen(text); m = strlen(pattern);
    getNext(pattern,m);    //计算pattern的next数组 
    int j = -1;   
    for(int i = 0; i < n; i++){
        while(j != -1 && text[i] != pattern[j+1]){            
            j = next[j];  //j回退使得满足条件或回到原点 
        }
        if(text[i] == pattern[j+1]){
            j++;   //匹配成功,j指向已匹配的最后一位             
        }
        if(j == m-1){
            return true;   //已全部匹配完成 
        }        
    } 
    return false;  //匹配结束,失败       
}

  可以发现,求解next数组的过程其实就是模式串pattern进行自我匹配的过程。故上述代码与求解next数组的代码极为类似。

2.2 KMP算法实现统计出现次数

        (模式串可能有重叠。例:文本串“abababab”中模式串“abab”出现了3次)

  每次成功匹配统计次数的变量加1,成功匹配之后i = i+1,j 回退使得pattern[j+1] == text[i]。直接贴代码:

//KMP算法  统计pattern在text出现的次数 
bool KMP(char text[],char pattern[]) {
    int n = strlen(text); m = strlen(pattern);
    getNext(pattern,m);    //计算pattern的next数组 
    int j = -1,ans = 0;   
    for(int i = 0; i < n; i++){
        while(j != -1 && text[i] != pattern[j+1]){            
            j = next[j];  //j回退使得满足条件或回到原点 
        }
        if(text[i] == pattern[j+1]){
            j++;   //匹配成功,j指向已匹配的最后一位             
        }
        if(j == m-1){
            ans++;
            j = next[j]; 
        }        
    } 
    return ans;    
}

2.3 时间复杂度分析

  for语句循环了n次,复杂度为O(n)。在每一个for循环内,j要么自增1,要么减小。由于减小到最低为-1。所以while循环对于整个过程最多循环n次,平均每次是O(1)。因此可认为for语句的时间复杂度为O(n)。考虑到计算next数组需要O(m)的时间复杂度(用同样的分析方法),因此KMP算法总共需要O(m+n)的时间复杂度。