字符串模式匹配问题——KMP算法

KMP算法详解

其他相关模式匹配算法：

RK算法

BM算法

KMP算法基本原理

KMP算法是目前解决字符串匹配最常用的方法，其克服了暴力算法出现不匹配时的回溯问题。

我们可以类比BM算法，将不能匹配的那个字符仍然叫作坏字符，把已经匹配的那段字符串叫作好前缀。当我们遇到坏字符时，就开始滑动模式串，将好前缀的后缀子串和模式串的前缀子串比较是否相同，寻找最长的相同的子串。因此KMP算法可以尽可能地让模式串移动到有效的位置。即在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。

我们要记好这句将好前缀的后缀子串和模式串的前缀子串比较，寻找最长的相同的子串，当然你也可以描述为拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的。这句话的内涵其实就是我们后面要求的next[ ]数组的内涵，很重要。

假设最长的可匹配的那部分前缀子串长度是 k。我们把模式串一次性往后滑动 j-k 位，相当于，每次遇到坏字符的时候，我们就把 j 更新为 k，i 不变，然后继续比较。

为了表述起来方便，我把好前缀的所有后缀子串中，最长的可匹配前缀子串的那个后缀子串，叫作最长可匹配后缀子串；对应的前缀子串，叫作最长可匹配前缀子串。

比如上述示例：

当好前缀为： a b a b a

则最长可匹配后缀子串为：a b a

​ 最长可匹配前缀子串为：a b a

KMP算法流程：

• 假设现在主串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 值，即移动的实际位数为：j - next[j]，且此值大于等于1。

next 数组值的含义：代表模式串中当前字符之前的字符串中，有多大长度的相同前缀后缀。

当然有的文章中将next数组的含义描述为：模式串中每个前缀（这些前缀都有可能是好前缀）的最长可匹配前缀子串的结尾字符下标。（注意：采用此含义定义的next2数组和上一种的定义的next1数组结果不同,从而KMP算法也有一点小改 )

个人认为第一种next数组含义比较好理解，因此以此定义描述。

例如下图所示：如果next [j] = k，代表 j 之前的字符串中有最大长度为k 的相同前缀后缀。这很重要！因为如此我们就可以将P 串的原来与前缀匹配的部分 移动至 后缀部分，从此开始重新匹配。

综上，KMP的 next 数组相当于告诉我们：当模式串中的某个字符跟文本串中的某个字符匹配失配时，模式串下一步应该滑动到哪个位置。如模式串中在j 处的字符跟文本串在i 处的字符匹配失配时，下一步用next [j] 处的字符继续跟文本串i 处的字符匹配，相当于模式串向右移动 j - next[j] 位。

结论：失配时，模式串向右移动的位数为：已匹配字符数 - 失配字符的上一位字符所对应的最大相同前缀后缀长度值

假如，本文串与模式串已经匹配到此时状态，此时匹配不成功，需要移动模式串，移动位数 = 已经匹配字符(6) - 以’B’结尾的最大相同前缀后缀长度值(2) = 4

求取next数组

我们根据next数组的定义：模式串**当前字符之前的字符串中，有多大长度的相同前缀后缀。**因此只要能够求出字符串的前后缀最大公共元素，即可因此填写next数组。假设模式串P ：ABCDABD,则前后缀最大公共元素长度如下：

根据此变换为next数组定义，因为是当前字符之前的字符串，有多大长度的相同前缀后缀。所以只需要将其向右移一位，并在开头填补 -1

因此，我们可由以上结论“失配时模式串向右移动的位数为：已匹配字符数 - 失配字符的上一位字符所对应的最大相同前缀后缀长度值 ”变为 “ 失配时，模式串向右移动的位数为：失配字符所在位置 - 失配字符所对应的next 值”

！！！最复杂的部分，也就是 next 数组是如何计算出来的

我们可以用非常笨的方法，比如要计算模式串 b 的 next[4]，我们就把 b[0, 3]的所有后缀子串，从长到短找出来，依次看看，是否能跟模式串的前缀子串匹配。很显然，这个方法也可以计算得到 next 数组，但是效率非常低。

我们看到，当我们在求next[4]时，next[0…3]已经求出来了，因此我们可以根据已有的信息来求next[4]。

那么问题便转为：已知next [0, …, j]，如何求出**next [j + 1]**呢？

对于P的前j+1个序列字符：

• 若p[k] == p[j]，则next[j + 1 ] = next [j] + 1 = k + 1；
• 若p[k ] ≠ p[j]，如果此时p[ next[k] ] == p[j ]（递归），则next[ j + 1 ] = next[k] + 1，否则继续递归前缀索引k = next[k]，而后重复此过程。 相当于在字符p[j+1]之前不存在长度为k+1的前缀"p0 p1, …, pk-1 pk"跟后缀“pj-k pj-k+1, …, pj-1 pj"相等，那么是否可能存在另一个值t+1 < k+1，使得长度更小的前缀 “p0 p1, …, pt-1 pt” 等于长度更小的后缀 “pj-t pj-t+1, …, pj-1 pj” 呢？如果存在，那么这个t+1 便是next[ j+1]的值，此相当于利用已经求得的next 数组（next [0, …, k, …, j]）进行P串前缀跟P串后缀的匹配。

对于：p[k] == p[j]，则next[j + 1 ] = next [j] + 1 = k + 1的结论证明如下：

我们在比较[pk] == p[j]时，说明前面已经匹配,即p[0…(k-1)] == p[(j-k)…(j-1)]，此时next[j] = k，从而得出p[0…(k)] == p[(j-k)…(j)]，即next[j+1] == k + 1 = next[j]+1;

​ 如果pk != pj 呢？那为何递归前缀索引k = next[k]，就能找到长度更短的相同前缀后缀呢？这又归根到next数组的含义。我们拿前缀 p0 pk-1 pk 去跟后缀pj-k pj-1 pj匹配，如果pk 跟pj 失配，下一步就是用p[next[k]] 去跟pj 继续匹配，如果p[ next[k] ]跟pj还是不匹配，则需要寻找长度更短的相同前缀后缀，即下一步用p[ next[ next[k] ] ]去跟pj匹配。此过程相当于模式串的自我匹配，所以不断的递归k = next[k]，直到要么找到长度更短的相同前缀后缀，要么没有长度更短的相同前缀后缀。

举一个能在前缀中找到字符D的例子呢？OK，咱们便来看一个能在前缀中找到字符D的例子，如下图所示：

既然没有长度为4的相同前缀后缀，咱们可以寻找长度短点的相同前缀后缀，最终，因在p0处发现也有个字符D，p0 = pj，所以p[j]对应的长度值为1，相当于E对应的next 值为1（即字符E之前的字符串“DABCDABD”中有长度为1的相同前缀和后缀）。

求取next代码如下：

/*
@param: p 模式串
@param: 返回next数组
*/
vector<int> getnext(string p){
    int len = p.size();
    vector<int> next(len);
    int k = -1;
    int j = 0;
    next[0] = -1;
    while (j < len - 1){
        //p[k]: 表示前缀的结尾
        //p[j]：表示后缀的结尾
        if (k == -1 || p[k] == p[j]){
            ++j;
            ++k;
            //等价于 next[j] = p[k] == p[j] ? next[k] : k;
            if (p[k] != p[j]){
                next[j] = k;
            }else{
                next[j] = next[k]; //因为如果p[k] == p[j]，那么也会移动后也会失配（因为本次已经失配）
            }
        }else{
            //寻找字符k前的公共前缀后缀长度
            k = next[k];
        }
    }
    return next;
}
           

对next数组的小优化

我们看到上面代码多了一句 next[j] = next[k]; 这是什么意思呢？

因为如果p[k] == p[j]，那么也会移动后也会失配（因为本次已经失配）如图

此时处于失配状态，如果用之前的next 数组方法求模式串“abab”的next 数组，可得其next 数组为-1 0 0 1（0 0 1 2整体右移一位，初值赋为-1），当它跟下图中的文本串去匹配的时候，发现b跟c失配，于是模式串右移j - next[j] = 3 - 1 =2位。

右移2位后，如图：

b又跟c失配。事实上，因为在上一步的匹配中，已经得知p[3] = b，与s[3] = c失配，而右移两位之后，让p[ next[3] ] = p[1] = b 再跟s[3]匹配时，必然失配。

问题出在不该出现p[j] = p[ next[j] ]。为什么呢？理由是：当p[j] != s[i] 时，下次匹配必然是p[ next [j]] 跟s[i]匹配，如果p[j] = p[ next[j] ]，必然导致后一步匹配失败（因为p[j]已经跟s[i]失配，然后你还用跟p[j]等同的值p[next[j]]去跟s[i]匹配，很显然，必然失配），所以不能允许p[j] = p[ next[j ]]。如果出现了p[j] = p[ next[j] ]咋办呢？如果出现了，则需要再次递归，即令next[j] = next[ next[j] ]。

求出了next数组后，我们就可以根据next数组进行匹配了，代码如下：

/*
@param s:主串
@param p:模式串
*/
int KMP(string s,string p){
    int lens = s.size();
    int lenp = p.size();
    //如果有空串，直接匹配失败
    if (lens == 0 || lenp == 0){
        return -1;
    }
    vector<int> next = getnext(p);
    //i: 主串下标
    //j:模式串下标
    int i = 0,j = 0
    while (i < lens && j < lenp)
    {
        if (j == -1 || s[i] == p[j]){
            i++;
            j++;
        }else{
            //模式串向右滑动 j - next[j]等价于 j = next[j]
            j = next[j];
        }
    }
	return j == lenp ? i - j : -1;
}
           

KMP算法复杂度分析

空间复杂度：

空间复杂度很容易分析，KMP 算法只需要一个额外的 next 数组，数组的大小跟模式串相同。所以空间复杂度是 O(m)，m 表示模式串的长度。

时间复杂度：

因为KMP算法涉及到两部分，一部分是求next数组，另一部分是借助next数组进行匹配。

• 求next数组：next 数组计算的时间复杂度是 O(m)。
• 进行匹配：while 循环中的这条语句总的执行次数不会超过 n（主串长度），所以这部分的时间复杂度是 O(n)

因此总的时间复杂度为O(n + m)

相关参考文章：https://blog.csdn.net/v_july_v/article/details/7041827#t10