对字符串模式匹配KMP算法的教学方法设计

2022-09-11

字符串模式匹配是各种串处理系统中重要的操作之一。KMP算法是模式匹配算法中性能较优的算法, 但也是较难懂和难讲的算法;在实际的教学中应该在分析完算法思想的基础上从实际举例入手, 首先理解并熟悉手工算法, 进而掌握算法思想, 最终完整掌握算法本身。

1 KMP算法思想分析

首先假设主串为‘s1s2…sn’, 模式串为‘p1p2…pm’, 我们从主串的第1个字符起开始匹配, 当主串中第i个字符与模式串中第j个字符“失配” (即比较不等) 时, 主串中第i个字符 (i指针不回溯) 应与模式串中哪个字符再比较?

假设此时应与模式串中第k (kk满足下列关系式 (1)

反之, 若模式串中存在满足式 (3) 的两个子串, 则当匹配过程中, 主串第i个字符与模式串中第j个字符比较不等时, 仅需将模式串向右滑动至模式串中第k个字符和主串中第i个字符对齐, 此时, 模式串前k-1个字符的字串‘p1p2…pk-1’必定与主串中第i个字符之前长度为k-1的子串‘si-k+1si-k+2…si-1’相等, 匹配仅需从模式串中第k个字符与主串中第i个字符比较继续进行。

若令next[j]=k, 则next[j]表明当模式中第j个字符与主串中相应字符不相等时, 在模式中需重新和主串中该字符进行比较的字符的位置, 这一位置只与模式串本身有关而与主串中的字符无关。由此模式串的next函数的定义为:

2 next函数的求解推理及实例设计

对任何模式串p, 只要确定next[i] (i=1, …, m) 的值, 当pi≠tj时, 直接右移inext[i]个字符, 使pk (即pnext[i]) 与tj比较, 或使p0与tj+1比较。显然, 不论主串是什么, 在进行字符串匹配之前首先要求得next数组的值。

求next数组第i个元素的值, 实际上就是模式串p中最大相同的前缀与后缀的长度k, 其过程也是一个推理的过程, 分析如下:

根据next函数的定义 (式4) , next[1]的值为0;

假设:next[j]=k;又模式串p的第j个字符与第k个字符相等, 则next[j+1]=k+1;

若:pj≠pk, 则需往前回溯, 检查模式串p的第j个字符与第几个字符相等?这实际上也是一个匹配的过程, 不同在于:主串和模式串是同一个串;

此时, 已有‘p1p2…pk-1’=pj-k+1pj-k+2…pj-1’, 当pj≠pk时应将模式向右滑动至以模式中的第next[k]个字符和主串 (实际上也是模式串本身) 中的第j个字符相比较。若next[k]=h, 且pj=ph, 则说明在主串中第j+1个字符之前存在一个长度为h (即next[k]) 的最长子串, 和模式串中从首字符其长度为h的子串相等, 即‘p1p2…ph’=pj-h+1pj-k+2…pj-1’ (1

同理, 若pj≠ph, 这将模式继续向右滑动直至将模式中第next[h]个字符和pj对齐, ……, 以此类推, 直至pj和模式中某个字符匹配成功或者不存在任何h (1

例如, 有模式串p=‘ababcabababc’, 其对应的next函数值如表1。

根据以上分析, 显然next[1]=0;

而所有next[j]>1的字符均说明在该字符前分别存在有长度为next[j]-1的前缀子串和后缀子串, 比如next[9]=4, 说明在模式串的第9个字符‘b’之前存在两个长度为3的子串相等, 即‘p1p2p3’=‘p6p7p8’, 均为‘aba’;

所有next[j]=1的字符意味着在该字符之前不存在任何长度的两个子串相等, 比如next[6]=1, 即说明在模式串的第6个字符‘a’之前不存在任何长度的前缀和后缀相等。