字符串中的模式匹配（Pattern Matching) 以及KMP详解

type

status

一、模式匹配（Pattern Matching）简介

模式匹配是数据结构中字符串的一种基本操作，它用于在一条字符串中寻找与另一条子串相同的所有子串。

例如在"hjh123abc"中寻找"hjh"

二、简单模式匹配

暴力匹配

思想：用计数指针i和j分别指示主串和子串待比较字符位置。

从主串第一个字符开始，使用模式串进行匹配

相等则接着检查后续字符，不相等，则模式串的j返回第一个字符，主串从下个字符开始接着比较

最坏时间复杂度：

n和m分别为主串和模式串的长度

简单模式匹配的缺点：

时间复杂度大，因为每次匹配失败主串指针都要回溯到刚开始的位置的下一个位置重新开始匹配

如果已匹配相等的前缀序列中有某个后缀刚好是模式的前缀，那么主串指针就不用重新回溯

三、利用部分匹配值表快速匹配

KMP算法的改进思路

主串指针不回溯，只有模式串的指针回溯

几个概念

前缀：除最后一个字符外，字符串的所有头部子串

后缀：除第一个字符外，字符串所有尾部子串

部分匹配值：字符串前缀和后缀的最长相等前后缀长度

举例：”abcac”

通过部分匹配值，我们可以得到部分匹配值的表

可以通过以下公式，配合部分匹配值算出子串需要后移的位数

举例

发生匹配失败，则查表可知最后一个匹配的字符b的部分匹配值为0，所以移动位数

发生匹配失败，最后一个匹配字符a的部分匹配值为1，所以移动位数

匹配成功

此算法可以在时间数量级上完成串的匹配操作

公式原理是什么？

如图，，因为模式串a开头，不是bc，且与后缀a相同所以可以直接在主串中跳过bc

认真思考下：什么是部分匹配值？

通过我们计算部分匹配值的过程，是通过前缀和后缀相同的最长子序列得到的，所以部分匹配值相当于我们在匹配的时候，匹配失败了，但是开头的一部分在匹配的那部分的结尾有体现，可以直接接着用。

例如说

部分匹配值表

移动位数=已经匹配了的字符数-末尾可以接着用来匹配的字符数

四、改进的模式匹配——KMP算法

通过上面的方法，那么我们就可以对简单模式匹配进行算法改进了！

为什么KMP用到了next数组

我们使用部分匹配表的时候，都是看匹配失败了的那个字符的前一个字符的部分匹配值，这样不太方便，倒不如把PM表右移一位，就不用去找匹配失败了的那个字符的前一个字符了

部分匹配值表

对应的next数组

第一个元素右移以后的空缺用-1代替

因为如果第一个匹配失败了，那么我们需要将主串右移一位

右移位数=

最后一个元素溢出了

因为最后一个元素的部分匹配值是给他后面一个元素用的，显然没有下一个元素了，所以可以舍去

于是得到

子串的指针变化：

j指针-需要移动的位数

为了使得公式简洁，把next数组整体+1

最后得到了子串指针变化公式

公式含义：在子串第j个字符与主串发生失配时，跳到子串的next[j]位置重新与主串当前位置进行比较

next数组的快速求法

next[1]=0

next[2]=1

next[j]=S的最长相等前后缀长度+1

求next数组算法实现

KMP算法实现

虽然说普通匹配的时间复杂度为O(mn)，KMP为O(m+n)但一般情况下普通模式匹配算法实际执行近似于O(m+n)所以至今依然被使用。

五、KMP算法的进一步优化

KMP算法存在一个问题

当"aaaab"与 "aaabaaaab"匹配时

在4位置匹配失败的后，还进行了3次比较，这是存在的问题

所以有人提出了使用nextval数组来解决这个问题

那么这个nextval数组是怎么求的呢？

观察下表

从下标j为1开始向右

j=1的时候，next[j]肯定为0, nextval[j]也为0

然后依次向后观察，如果下一个的next[j]所指向的字符与j所指向的字符相同，则把nextval[j]修改为next[j],不同则保持不变

例如

nextval数组求法

六、程序演示

注：算法中下标都从1开始，为了方便我用数组存的，下标从0开始，所以部分位置有+1或者-1操作，思路是算法的思路

简单模式匹配

Output:

KMP算法

Output:

注：得到的结果里next数组为-1 0 0 0 1是因为实现的时候下标从0开始

七、参考资料

《数据结构考研复习指导》——王道论坛