串的模式匹配之KMP算法

串的模式匹配之KMP算法

朴素模式匹配算法的问题

在之前我们介绍过串的朴素模式匹配算法，基本思路就是用主串中的每一个子串和模式串匹配，若匹配失败，都是模式串后移一位再重新开始比较，将模式串序号j置为1。我们假设主串的长度为m，模式串的长度为n，那么在最坏的情况下，主串中每个子串都和模式串进行了匹配，时间复杂度就为O(mn)。

为了方便理解，这里举一个栗子🌰，假设在主串a b a b c a b c a c b a b中匹配模式串a b c a c，朴素模式匹配算法的步骤如下

• 从i=1，j=1开始匹配，当i=3，j=3时匹配失败，于是j置为1，i回溯，再从i=2开始匹配
• i=2，j=1时发现第一个字符就不匹配，于是j置为1，再从i=3开始匹配
• i=3，j=1开始匹配，这次前期很顺利，直到i=7，j=5时，发现匹配失败。于是j置为1，i回溯到i=4的位置，再从i=4，j=1匹配

好了到这里我们暂停，相信这里已经可以体现出KMP的问题了，从i=3开始匹配时，连续4个字符都可以匹配上，直到j=5匹配失败，于是i从7回到3，j置为1。

在暴力匹配中，每次匹配失败都是模式串后移一位再从头开始比较，而如果某个已经匹配相等的字符序列是模式串的某个前缀，这种重复比较就相当于是模式串在不断的自我比较，这也就是其低效率的原因。

基本思路

前缀，后缀，部分匹配值的概念

在正式讲思路前，我们先了解一下什么是前缀，后缀。

• 前缀：除了最后一个字符外，字符串的所有头部子串
• 后缀：除了第一个字符外，字符串的所有尾部子串
• 部分匹配值：字符串的前缀和后缀的最长相等前后缀长度

举个栗子🌰：字符串a b a b a

• a的前缀和后缀都为∅，部分匹配值为0
• ab的前缀为a，后缀为b，最长相等前后缀长度0，所以部分匹配值为0
• aba的前缀为{a,ab}，后缀为{a,ba}，部分匹配值为1
• abab的前缀为{a,ab,aba}，后缀为{b,ab,bab}，部分匹配值为2
• ababa的前缀为{a,ab,aba,abab}，后缀为{a,ba,aba,baba}，部分匹配值为3（aba）

通过上述方法我们也可以求出一开始例子中模式串abcac的部分匹配值，我们汇总成表格，称为部分匹配值表（PM表）

部分匹配值的作用

刚刚提到，低效率的原因是某个已匹配相等的字符是某个模式串的前缀，这样再按部就班的比较相当于一直是模式串的自我比较。那我们这样想：如果已匹配相等的前缀序列中有某个后缀正好是模式串的前缀，那么我们就可以将模式串直接移动到这个后缀的位置。这就是KMP算法的主要思路。

那么如何来实现这个思路呢？这就要用到刚刚求出的部分匹配值了。我们先给出公式，再做解释

移动位数=已匹配字符数-对应的部分匹配值

拿刚刚的例子继续说，假如我们从i=1,j=1开始匹配：

当i=3，j=3时匹配失败，此时已匹配的字符数为2，而字符2对应的部分匹配值是0，所以移动位数=2-0=2，子串向后移动两位

当i=7，j=5时匹配失败，此时已匹配字符数为4，其对应的部分匹配值为1，所以可以算出移动位数=4-1=3，子串向后移动三位

公式的原理

移动位数 = 已匹配字符数 - 对应的部分匹配值

算法改进

之前算法是：每当匹配失败，就去看它前一个字符的部分匹配值，我们如果将PM表整体右移一位，这样哪个元素匹配失败，就直接看它自己的部分匹配值即可。拿刚刚字符串abcac来说，右移一位后PM表变为：

• 若第一个元素匹配失败，则直接右移一位，不需要计算移动位数
• 在右移的过程中最后一个元素的部分匹配值溢出，但原先最后一个元素的部分匹配值是给下一个元素使用的，但最后一个元素没有下一个元素了，所以可以舍去。

所以公式可以改写为：

移动位数 = 已匹配字符数 - 自己的部分匹配值

则发送匹配失败时，j的变化为：j = j - Move = j - ( (j-1) - next[j] ) + 1 = next[j] + 1

代码实现

KMP的算法实现起来非常简短，以至于我第一次看见时觉得很不可思议，如此简短的代码就可以实现这么庞大的功能。但当我仔细去看这个代码时，真的是看不懂，但好在b站上有一个很详细的视频，跟着一步步走也算是搞明白了。下面我们先贴出代码，在做解释：

//KMP
void getnext(SString T,int next[]);
int index_KMP(SString S,SString T){
    int i = 1,j = 1;
    int next[T.length+1];
    getnext(T,next);
    while (i<=S.length && j<=T.length){
        if(j==0 || S.ch[i]==T.ch[j]){
            i++;
            j++;
        }
        else
            j = next[j];
    }
    if(j>T.length)
        return i - T.length;
    else
        return 0;
}
//求next数组
void getnext(SString T,int next[]){
    int i = 1, j = 0;
    next[1] = 0;
    while (i<T.length){
        if(j==0 || T.ch[i]==T.ch[j]){
            i++;
            j++;
            next[i] = j;
        }
        else
            j = next[j];
    }
}

以后复习去看这个视频吧，脑袋实在成浆糊了，写不动了。。。https://www.bilibili.com/video/BV16X4y137qw/?spm_id_from=333.337.search-card.all.click&vd_source=ef7dc76f807d26d86d33be41cf55ea77