免费网站电视剧全免费的app,现在网站建设尺寸一般多少,自媒体平台注册入口,深圳软件外包公司有哪些从头到尾彻底理解KMP 作者#xff1a;July 时间#xff1a;最初写于2011年12月#xff0c;2014年7月21日晚10点 全部删除重写成此文#xff0c;随后的半个多月不断反复改进。后收录于新书《编程之法#xff1a;面试和算法心得》第4.4节中。 1. 引言 本KMP原文最初写于2年多… 从头到尾彻底理解KMP 作者July 时间最初写于2011年12月2014年7月21日晚10点 全部删除重写成此文随后的半个多月不断反复改进。后收录于新书《编程之法面试和算法心得》第4.4节中。 1. 引言 本KMP原文最初写于2年多前的2011年12月因当时初次接触KMP思路混乱导致写也写得混乱。所以一直想找机会重新写下KMP但苦于一直以来对KMP的理解始终不够故才迟迟没有修改本文。 然近期因开了个算法班班上专门讲解数据结构、面试、算法才再次仔细回顾了这个KMP在综合了一些网友的理解、以及算法班的两位讲师朋友曹博、邹博的理解之后写了9张PPT发在微博上。随后一不做二不休索性将PPT上的内容整理到了本文之中后来文章越写越完整所含内容早已不再是九张PPT 那样简单了。 KMP本身不复杂但网上绝大部分的文章包括本文的2011年版本把它讲混乱了。下面咱们从暴力匹配算法讲起随后阐述KMP的流程 步骤、next 数组的简单求解 递推原理 代码求解接着基于next 数组匹配谈到有限状态自动机next 数组的优化KMP的时间复杂度分析最后简要介绍两个KMP的扩展算法。 全文力图给你一个最为完整最为清晰的KMP希望更多的人不再被KMP折磨或纠缠不再被一些混乱的文章所混乱。有何疑问欢迎随时留言评论thanks。 2. 暴力匹配算法 假设现在我们面临这样一个问题有一个文本串S和一个模式串P现在要查找P在S中的位置怎么查找呢 如果用暴力匹配的思路并假设现在文本串S匹配到 i 位置模式串P匹配到 j 位置则有
如果当前字符匹配成功即S[i] P[j]则ij继续匹配下一个字符如果失配即S[i]! P[j]令i i - (j - 1)j 0。相当于每次匹配失败时i 回溯j 被置为0。理清楚了暴力匹配算法的流程及内在的逻辑咱们可以写出暴力匹配的代码如下
int ViolentMatch(char* s, char* p){ int sLen strlen(s); int pLen strlen(p); int i 0; int j 0; while (i sLen j pLen){ if (s[i] p[j]){ //①如果当前字符匹配成功即S[i] P[j]则ij i;j;} else{ //②如果失配即S[i]! P[j]令i i - (j - 1)j 0 i i - j 1;j 0;}} //匹配成功返回模式串p在文本串s中的位置否则返回-1 if (j pLen) return i - j; else return -1;} 举个例子如果给定文本串S“BBC ABCDAB ABCDABCDABDE”和模式串P“ABCDABD”现在要拿模式串P去跟文本串S匹配整个过程如下所示 1. S[0]为BP[0]为A不匹配执行第②条指令“如果失配即S[i]! P[j]令i i - (j - 1)j 0”S[1]跟P[0]匹配相当于模式串要往右移动一位i1j0 2. S[1]跟P[0]还是不匹配继续执行第②条指令“如果失配即S[i]! P[j]令i i - (j - 1)j 0”S[2]跟P[0]匹配i2j0从而模式串不断的向右移动一位不断的执行“令i i - (j - 1)j 0”i从2变到4j一直为0 3. 直到S[4]跟P[0]匹配成功i4j0此时按照上面的暴力匹配算法的思路转而执行第①条指令“如果当前字符匹配成功即S[i] P[j]则ij”可得S[i]为S[5]P[j]为P[1]即接下来S[5]跟P[1]匹配i5j1 4. S[5]跟P[1]匹配成功继续执行第①条指令“如果当前字符匹配成功即S[i] P[j]则ij”得到S[6]跟P[2]匹配i6j2如此进行下去 5. 直到S[10]为空格字符P[6]为字符Di10j6因为不匹配重新执行第②条指令“如果失配即S[i]! P[j]令i i - (j - 1)j 0”相当于S[5]跟P[0]匹配i5j0 6. 至此我们可以看到如果按照暴力匹配算法的思路尽管之前文本串和模式串已经分别匹配到了S[9]、P[5]但因为S[10]跟P[6]不匹配所以文本串回溯到S[5]模式串回溯到P[0]从而让S[5]跟P[0]匹配。 而S[5]肯定跟P[0]失配。为什么呢因为在之前第4步匹配中我们已经得知S[5] P[1] B而P[0] A即P[1] ! P[0]故S[5]必定不等于P[0]所以回溯过去必然会导致失配。那有没有一种算法让i 不往回退只需要移动j 即可呢 答案是肯定的。这种算法就是本文的主旨KMP算法它利用之前已经部分匹配这个有效信息保持i 不回溯通过修改j 的位置让模式串尽量地移动到有效的位置。 3. KMP算法
3.1 定义 Knuth-Morris-Pratt 字符串查找算法简称为 “KMP算法”常用于在一个文本串S内查找一个模式串P 的出现位置这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表故取这3人的姓氏命名此算法。 下面先直接给出KMP的算法流程如果感到一点点不适没关系坚持下稍后会有具体步骤及解释越往后看越会柳暗花明☺
假设现在文本串S匹配到 i 位置模式串P匹配到 j 位置 如果j -1或者当前字符匹配成功即S[i] P[j]都令ij继续匹配下一个字符如果j ! -1且当前字符匹配失败即S[i] ! P[j]则令 i 不变j next[j]。此举意味着失配时模式串P相对于文本串S向右移动了j - next [j] 位。 换言之当匹配失败时模式串向右移动的位数为失配字符所在位置 - 失配字符对应的next 值next 数组的求解会在下文的3.3.3节中详细阐述即移动的实际位数为j - next[j]且此值大于等于1。很快你也会意识到next 数组各值的含义代表当前字符之前的字符串中有多大长度的相同前缀后缀。例如如果next [j] k代表j 之前的字符串中有最大长度为k 的相同前缀后缀。 此也意味着在某个字符失配时该字符对应的next 值会告诉你下一步匹配中模式串应该跳到哪个位置跳到next [j] 的位置。如果next [j] 等于0或-1则跳到模式串的开头字符若next [j] k 且 k 0代表下次匹配跳到j 之前的某个字符而不是跳到开头且具体跳过了k 个字符。 转换成代码表示则是
int KmpSearch(char* s, char* p){ int i 0; int j 0; int sLen strlen(s); int pLen strlen(p); while (i sLen j pLen){ //①如果j -1或者当前字符匹配成功即S[i] P[j]都令ij if (j -1 || s[i] p[j]){i;j;} else{ //②如果j ! -1且当前字符匹配失败即S[i] ! P[j]则令 i 不变j next[j] //next[j]即为j所对应的next值 j next[j];}} if (j pLen) return i - j; else return -1;} 继续拿之前的例子来说当S[10]跟P[6]匹配失败时KMP不是跟暴力匹配那样简单的把模式串右移一位而是执行第②条指令“如果j ! -1且当前字符匹配失败即S[i] ! P[j]则令 i 不变j next[j]”即j 从6变到2后面我们将求得P[6]即字符D对应的next 值为2所以相当于模式串向右移动的位数为j - next[j]j - next[j] 6-2 4。 向右移动4位后S[10]跟P[2]继续匹配。为什么要向右移动4位呢因为移动4位后模式串中又有个“AB”可以继续跟S[8]S[9]对应着从而不用让i 回溯。相当于在除去字符D的模式串子串中寻找相同的前缀和后缀然后根据前缀后缀求出next 数组最后基于next 数组进行匹配不关心next 数组是怎么求来的只想看匹配过程是咋样的可直接跳到下文3.3.4节。 3.2 步骤
①寻找前缀后缀最长公共元素长度 对于P p0 p1 ...pj-1 pj寻找模式串P中长度最大且相等的前缀和后缀。如果存在p0 p1 ...pk-1 pk pj- k pj-k1...pj-1 pj那么在包含pj的模式串中有最大长度为k1的相同前缀后缀。举个例子如果给定的模式串为“abab”那么它的各个子串的前缀后缀的公共元素的最大长度如下表格所示比如对于字符串aba来说它有长度为1的相同前缀后缀a而对于字符串abab来说它有长度为2的相同前缀后缀ab相同前缀后缀的长度为k 1k 1 2。
②求next数组 next 数组考虑的是除当前字符外的最长相同前缀后缀所以通过第①步骤求得各个前缀后缀的公共元素的最大长度后只要稍作变形即可将第①步骤中求得的值整体右移一位然后初值赋为-1如下表格所示比如对于aba来说第3个字符a之前的字符串ab中有长度为0的相同前缀后缀所以第3个字符a对应的next值为0而对于abab来说第4个字符b之前的字符串aba中有长度为1的相同前缀后缀a所以第4个字符b对应的next值为1相同前缀后缀的长度为kk 1。
③根据next数组进行匹配 匹配失配j next [j]模式串向右移动的位数为j - next[j]。换言之当模式串的后缀pj-k pj-k1, ..., pj-1 跟文本串si-k si-k1, ..., si-1匹配成功但pj 跟si匹配失败时因为next[j] k相当于在不包含pj的模式串中有最大长度为k 的相同前缀后缀即p0 p1 ...pk-1 pj-k pj-k1...pj-1故令j next[j]从而让模式串右移j - next[j] 位使得模式串的前缀p0 p1, ..., pk-1对应着文本串 si-k si-k1, ..., si-1而后让pk 跟si 继续匹配。如下图所示综上KMP的next 数组相当于告诉我们当模式串中的某个字符跟文本串中的某个字符匹配失配时模式串下一步应该跳到哪个位置。如模式串中在j 处的字符跟文本串在i 处的字符匹配失配时下一步用next [j] 处的字符继续跟文本串i 处的字符匹配相当于模式串向右移动 j - next[j] 位。 接下来分别具体解释上述3个步骤。 3.3 解释
3.3.1 寻找最长前缀后缀 如果给定的模式串是“ABCDABD”从左至右遍历整个模式串其各个子串的前缀后缀分别如下表格所示 也就是说原模式串子串对应的各个前缀后缀的公共元素的最大长度表为下简称《最大长度表》 3.3.2 基于《最大长度表》匹配 因为模式串中首尾可能会有重复的字符故可得出下述结论 失配时模式串向右移动的位数为已匹配字符数 - 失配字符的上一位字符所对应的最大长度值下面咱们就结合之前的《最大长度表》和上述结论进行字符串的匹配。如果给定文本串“BBC ABCDAB ABCDABCDABDE”和模式串“ABCDABD”现在要拿模式串去跟文本串匹配如下图所示 1. 因为模式串中的字符A跟文本串中的字符B、B、C、空格一开始就不匹配所以不必考虑结论直接将模式串不断的右移一位即可直到模式串中的字符A跟文本串的第5个字符A匹配成功2. 继续往后匹配当模式串最后一个字符D跟文本串匹配时失配显而易见模式串需要向右移动。但向右移动多少位呢因为此时已经匹配的字符数为6个ABCDAB然后根据《最大长度表》可得失配字符D的上一位字符B对应的长度值为2所以根据之前的结论可知需要向右移动6 - 2 4 位。3. 模式串向右移动4位后发现C处再度失配因为此时已经匹配了2个字符AB且上一位字符B对应的最大长度值为0所以向右移动2 - 0 2 位。4. A与空格失配向右移动1 位。5. 继续比较发现D与C 失配故向右移动的位数为已匹配的字符数6减去上一位字符B对应的最大长度2即向右移动6 - 2 4 位。6. 经历第5步后发现匹配成功过程结束。通过上述匹配过程可以看出问题的关键就是寻找模式串中最大长度的相同前缀和后缀找到了模式串中每个字符之前的前缀和后缀公共部分的最大长度后便可基于此匹配。而这个最大长度便正是next 数组要表达的含义。
3.3.3 根据《最大长度表》求next 数组 由上文我们已经知道字符串“ABCDABD”各个前缀后缀的最大公共元素长度分别为 而且根据这个表可以得出下述结论
失配时模式串向右移动的位数为已匹配字符数 - 失配字符的上一位字符所对应的最大长度值上文利用这个表和结论进行匹配时我们发现当匹配到一个字符失配时其实没必要考虑当前失配的字符更何况我们每次失配时都是看的失配字符的上一位字符对应的最大长度值。如此便引出了next 数组。 给定字符串“ABCDABD”可求得它的next 数组如下 把next 数组跟之前求得的最大长度表对比后不难发现next 数组相当于“最大长度值” 整体向右移动一位然后初始值赋为-1。意识到了这一点你会惊呼原来next 数组的求解竟然如此简单就是找最大对称长度的前缀后缀然后整体右移一位初值赋为-1当然你也可以直接计算某个字符对应的next值就是看这个字符之前的字符串中有多大长度的相同前缀后缀。 换言之对于给定的模式串ABCDABD它的最大长度表及next 数组分别如下 根据最大长度表求出了next 数组后从而有 失配时模式串向右移动的位数为失配字符所在位置 - 失配字符对应的next 值而后你会发现无论是基于《最大长度表》的匹配还是基于next 数组的匹配两者得出来的向右移动的位数是一样的。为什么呢因为
根据《最大长度表》失配时模式串向右移动的位数 已经匹配的字符数 - 失配字符的上一位字符的最大长度值而根据《next 数组》失配时模式串向右移动的位数 失配字符的位置 - 失配字符对应的next 值 其中从0开始计数时失配字符的位置 已经匹配的字符数失配字符不计数而失配字符对应的next 值 失配字符的上一位字符的最大长度值两相比较结果必然完全一致。所以你可以把《最大长度表》看做是next 数组的雏形甚至就把它当做next 数组也是可以的区别不过是怎么用的问题。
3.3.4 通过代码递推计算next 数组 接下来咱们来写代码求下next 数组。 基于之前的理解可知计算next 数组的方法可以采用递推
1. 如果对于值k已有p0 p1, ..., pk-1 pj-k pj-k1, ..., pj-1相当于next[j] k。 ulli此意味着什么呢究其本质strongnext[j] k 代表p[j] 之前的模式串子串中有长度为k 的相同前缀和后缀/strong。有了这个next 数组在KMP匹配中当模式串中j 处的字符失配时下一步用next[j]处的字符继续跟文本串匹配相当于模式串向右移动j - next[j] 位。/li
/ul/li举个例子如下图根据模式串“ABCDABD”的next 数组可知失配位置的字符D对应的next 值为2代表字符D前有长度为2的相同前缀和后缀这个相同的前缀后缀即为“AB”失配后模式串需要向右移动j - next [j] 6 - 2 4位。 向右移动4位后模式串中的字符C继续跟文本串匹配。 2. 下面的问题是已知next [0, ..., j]如何求出next [j 1]呢对于P的前j1个序列字符
若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[j1]之前不存在长度为k1的前缀p0 p1, …, pk-1 pk跟后缀“pj-k pj-k1, …, pj-1 pj相等那么是否可能存在另一个值t1 k1使得长度更小的前缀 “p0 p1, …, pt-1 pt” 等于长度更小的后缀 “pj-t pj-t1, …, pj-1 pj” 呢如果存在那么这个t1 便是next[ j1]的值此相当于利用已经求得的next 数组next [0, ..., k, ..., j]进行P串前缀跟P串后缀的匹配。一般的文章或教材可能就此一笔带过但大部分的初学者可能还是不能很好的理解上述求解next 数组的原理故接下来我再来着重说明下。 如下图所示假定给定模式串ABCDABCE且已知next [j] k相当于“p0 pk-1” “pj-k pj-1” AB可以看出k为2现要求next [j 1]等于多少因为pk pj C所以next[j 1] next[j] 1 k 1可以看出next[j 1] 3。代表字符E前的模式串中有长度k1 的相同前缀后缀。 但如果pk ! pj 呢说明“p0 pk-1 pk” ≠ “pj-k pj-1 pj”。换言之当pk ! pj后字符E前有多大长度的相同前缀后缀呢很明显因为C不同于D所以ABC 跟 ABD不相同即字符E前的模式串没有长度为k1的相同前缀后缀也就不能再简单的令next[j 1] next[j] 1 。所以咱们只能去寻找长度更短一点的相同前缀后缀。 结合上图来讲若能在前缀“ p0 pk-1 pk ” 中不断的递归前缀索引k next [k]找到一个字符pk’ 也为D代表pk’ pj且满足p0 pk-1 pk pj-k pj-1 pj则最大相同的前缀后缀长度为k 1从而next [j 1] k’ 1 next [k ] 1。否则前缀中没有D则代表没有相同的前缀后缀next [j 1] 0。 那为何递归前缀索引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]直到要么找到长度更短的相同前缀后缀要么没有长度更短的相同前缀后缀。如下图所示 引用下一读者wudehua55555于本文评论下留言以辅助大家从另一个角度理解“ 一直以为博主在用递归求next数组时没讲清楚为何要用k next[k],仔细看了这个红黄蓝分区图才突然恍然大悟就是找到p[k]对应的next[k]根据对称性只需再判断p[next[k]]与p[j]是否相等即可于是令k next[k],这里恰好就使用了递归的思路。其实我觉得不要一开始就陷入递归的方法中换一种思路直接从考虑对称性入手可直接得出k next[k]而这正好是递归罢了。以上是一些个人看法非常感谢博主提供的解析非计算机的学生也能看懂虽然从昨晚9点看到了现在。高兴。” 所以因最终在前缀ABC中没有找到D故E的next 值为0 模式串的后缀ABDE 模式串的前缀ABC 前缀右移两位 ABC 读到此有的读者可能又有疑问了那能否举一个能在前缀中找到字符D的例子呢OK咱们便来看一个能在前缀中找到字符D的例子如下图所示 给定模式串DABCDABDE我们很顺利的求得字符D之前的“DABCDAB”的各个子串的最长相同前缀后缀的长度分别为0 0 0 0 1 2 3但当遍历到字符D要求包括D在内的“DABCDABD”最长相同前缀后缀时我们发现pj处的字符D跟pk处的字符C不一样换言之前缀DABC的最后一个字符C 跟后缀DABD的最后一个字符D不相同所以不存在长度为4的相同前缀后缀。 怎么办呢既然没有长度为4的相同前缀后缀咱们可以寻找长度短点的相同前缀后缀最终因在p0处发现也有个字符Dp0 pj所以p[j]对应的长度值为1相当于E对应的next 值为1即字符E之前的字符串“DABCDABD”中有长度为1的相同前缀和后缀。 综上可以通过递推求得next 数组代码如下所示
void GetNext(char* p,int next[]){ int pLen strlen(p);next[0] -1; int k -1; int j 0; while (j pLen - 1){ //p[k]表示前缀p[j]表示后缀 if (k -1 || p[j] p[k]) {k;j;next[j] k;} else {k next[k];}}} 用代码重新计算下“ABCDABD”的next 数组以验证之前通过“最长相同前缀后缀长度值右移一位然后初值赋为-1”得到的next 数组是否正确计算结果如下表格所示 从上述表格可以看出无论是之前通过“最长相同前缀后缀长度值右移一位然后初值赋为-1”得到的next 数组还是之后通过代码递推计算求得的next 数组结果是完全一致的。
3.3.5 基于《next 数组》匹配 下面我们来基于next 数组进行匹配。 还是给定文本串“BBC ABCDAB ABCDABCDABDE”和模式串“ABCDABD”现在要拿模式串去跟文本串匹配如下图所示 在正式匹配之前让我们来再次回顾下上文2.1节所述的KMP算法的匹配流程
“假设现在文本串S匹配到 i 位置模式串P匹配到 j 位置 ulli如果j -1或者当前字符匹配成功即S[i] P[j]都令ij继续匹配下一个字符/lili如果j ! -1且当前字符匹配失败即S[i] ! P[j]则令 i 不变j next[j]。此举意味着失配时模式串P相对于文本串S向右移动了j - next [j] 位。ulli换言之当匹配失败时模式串向右移动的位数为失配字符所在位置 - 失配字符对应的next 值即strong移动的实际位数为j - next[j]/strong且此值大于等于1。strong”/strong/li/ul/li
/ul/li1. 最开始匹配时 ulliP[0]跟S[0]匹配失败ulli所以执行“如果j ! -1且当前字符匹配失败即S[i] ! P[j]则令 i 不变j next[j]”所以j -1故转而执行“如果j -1或者当前字符匹配成功即S[i] P[j]都令ij”得到i 1j 0即P[0]继续跟S[1]匹配。/li/ul/liliP[0]跟S[1]又失配j再次等于-1i、j继续自增从而P[0]跟S[2]匹配。/liliP[0]跟S[2]失配后P[0]又跟S[3]匹配。/liliP[0]跟S[3]再失配直到P[0]跟S[4]匹配成功开始执行此条指令的后半段“如果j -1或者当前字符匹配成功即S[i] P[j]都令ij”。/li
/ul/li2. P[1]跟S[5]匹配成功P[2]跟S[6]也匹配成功, ...直到当匹配到P[6]处的字符D时失配即S[10] ! P[6]由于P[6]处的D对应的next 值为2所以下一步用P[2]处的字符C继续跟S[10]匹配相当于向右移动j - next[j] 6 - 2 4 位。3. 向右移动4位后P[2]处的C再次失配由于C对应的next值为0所以下一步用P[0]处的字符继续跟S[10]匹配相当于向右移动j - next[j] 2 - 0 2 位。4. 移动两位之后A 跟空格不匹配模式串后移1 位。5. P[6]处的D再次失配因为P[6]对应的next值为2故下一步用P[2]继续跟文本串匹配相当于模式串向右移动 j - next[j] 6 - 2 4 位。6. 匹配成功过程结束。匹配过程一模一样。也从侧面佐证了next 数组确实是只要将各个最大前缀后缀的公共元素的长度值右移一位且把初值赋为-1 即可。
3.3.6 基于《最大长度表》与基于《next 数组》等价 我们已经知道利用next 数组进行匹配失配时模式串向右移动 j - next [ j ] 位等价于已匹配字符数 - 失配字符的上一位字符所对应的最大长度值。原因是
j 从0开始计数那么当数到失配字符时j 的数值就是已匹配的字符数由于next 数组是由最大长度值表整体向右移动一位且初值赋为-1得到的那么失配字符的上一位字符所对应的最大长度值即为当前失配字符的next 值。但为何本文不直接利用next 数组进行匹配呢因为next 数组不好求而一个字符串的前缀后缀的公共元素的最大长度值很容易求。例如若给定模式串“ababa”要你快速口算出其next 数组乍一看每次求对应字符的next值时还得把该字符排除之外然后看该字符之前的字符串中有最大长度为多大的相同前缀后缀此过程不够直接。而如果让你求其前缀后缀公共元素的最大长度则很容易直接得出结果0 0 1 2 3如下表格所示 然后这5个数字 全部整体右移一位且初值赋为-1即得到其next 数组-1 0 0 1 2。
3.3.7 Next 数组与有限状态自动机 next 负责把模式串向前移动且当第j位不匹配的时候用第next[j]位和主串匹配就像打了张“表”。此外next 也可以看作有限状态自动机的状态在已经读了多少字符的情况下失配后前面读的若干个字符是有用的。 3.3.8 Next 数组的优化 行文至此咱们全面了解了暴力匹配的思路、KMP算法的原理、流程、流程之间的内在逻辑联系以及next 数组的简单求解《最大长度表》整体右移一位然后初值赋为-1和代码求解最后基于《next 数组》的匹配看似洋洋洒洒清晰透彻但以上忽略了一个小问题。 比如如果用之前的next 数组方法求模式串“abab”的next 数组可得其next 数组为-1 0 0 10 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 数组求法void GetNextval(char* p, int next[]){ int pLen strlen(p);next[0] -1; int k -1; int j 0; while (j pLen - 1){ //p[k]表示前缀p[j]表示后缀 if (k -1 || p[j] p[k]){j;k; //较之前next数组求法改动在下面4行 if (p[j] ! p[k])next[j] k; //之前只有这一行 else //因为不能出现p[j] p[ next[j ]]所以当出现时需要继续递归k next[k] next[next[k]]next[j] next[k];} else{k next[k];}}} 利用优化过后的next 数组求法可知模式串“abab”的新next数组为-1 0 -1 0。可能有些读者会问原始next 数组是前缀后缀最长公共元素长度值右移一位 然后初值赋为-1而得那么优化后的next 数组如何快速心算出呢实际上只要求出了原始next 数组便可以根据原始next 数组快速求出优化后的next 数组。还是以abab为例如下表格所示 只要出现了p[next[j]] p[j]的情况则把next[j]的值再次递归。例如在求模式串“abab”的第2个a的next值时如果是未优化的next值的话第2个a对应的next值为0相当于第2个a失配时下一步匹配模式串会用p[0]处的a再次跟文本串匹配必然失配。所以求第2个a的next值时需要再次递归next[2] next[ next[2] ] next[0] -1此后根据优化后的新next值可知第2个a失配时执行“如果j -1或者当前字符匹配成功即S[i] P[j]都令ij继续匹配下一个字符”同理第2个b对应的next值为0。
对于优化后的next数组可以发现一点如果模式串的后缀跟前缀相同那么它们的next值也是相同的例如模式串abcabc它的前缀后缀都是abc其优化后的next数组为-1 0 0 -1 0 0前缀后缀abc的next值都为-1 0 0。 然后引用下之前3.1节的KMP代码
int KmpSearch(char* s, char* p){ int i 0; int j 0; int sLen strlen(s); int pLen strlen(p); while (i sLen j pLen){ //①如果j -1或者当前字符匹配成功即S[i] P[j]都令ij if (j -1 || s[i] p[j]){i;j;} else{ //②如果j ! -1且当前字符匹配失败即S[i] ! P[j]则令 i 不变j next[j] //next[j]即为j所对应的next值 j next[j];}} if (j pLen) return i - j; else return -1;} 接下来咱们继续拿之前的例子说明整个匹配过程如下 1. S[3]与P[3]匹配失败。 2. S[3]保持不变P的下一个匹配位置是P[next[3]]而next[3]0所以P[next[3]]P[0]与S[3]匹配。 3. 由于上一步骤中P[0]与S[3]还是不匹配。此时i3jnext [0]-1由于满足条件j-1所以执行“i, j”即主串指针下移一个位置P[0]与S[4]开始匹配。最后jpLen跳出循环输出结果i - j 4即模式串第一次在文本串中出现的位置匹配成功算法结束。 3.4 KMP的时间复杂度分析 相信大部分读者读完上文之后已经发觉其实理解KMP非常容易无非是循序渐进把握好下面几点
如果模式串中存在相同前缀和后缀即pj-k pj-k1, ..., pj-1 p0 p1, ..., pk-1那么在pj跟si失配后让模式串的前缀p0 p1...pk-1对应着文本串si-k si-k1...si-1而后让pk跟si继续匹配。之前本应是pj跟si匹配结果失配了失配后令pk跟si匹配相当于j 变成了k模式串向右移动j - k位。因为k 的值是可变的所以我们用next[j]表示j处字符失配后下一次匹配模式串应该跳到的位置。换言之失配前是jpj跟si失配时用p[ next[j] ]继续跟si匹配相当于j变成了next[j]所以j next[j]等价于把模式串向右移动j - next [j] 位。而next[j]应该等于多少呢next[j]的值由j 之前的模式串子串中有多大长度的相同前缀后缀所决定如果j 之前的模式串子串中不含j有最大长度为k的相同前缀后缀那么next [j] k。如之前的图所示 接下来咱们来分析下KMP的时间复杂度。分析之前先来回顾下KMP匹配算法的流程
“KMP的算法流程
假设现在文本串S匹配到 i 位置模式串P匹配到 j 位置 如果j -1或者当前字符匹配成功即S[i] P[j]都令ij继续匹配下一个字符如果j ! -1且当前字符匹配失败即S[i] ! P[j]则令 i 不变j next[j]。此举意味着失配时模式串P相对于文本串S向右移动了j - next [j] 位。”我们发现如果某个字符匹配成功模式串首字符的位置保持不动仅仅是i、j如果匹配失配i 不变即 i 不回溯模式串会跳过匹配过的next [j]个字符。整个算法最坏的情况是当模式串首字符位于i - j的位置时才匹配成功算法结束。 所以如果文本串的长度为n模式串的长度为m那么匹配过程的时间复杂度为O(n)算上计算next的O(m)时间KMP的整体时间复杂度为O(m n)。 4. 扩展1BM算法 KMP的匹配是从模式串的开头开始匹配的而1977年德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了一种新的字符串匹配算法Boyer-Moore算法简称BM算法。该算法从模式串的尾部开始匹配且拥有在最坏情况下O(N)的时间复杂度。在实践中比KMP算法的实际效能高。 BM算法定义了两个规则
坏字符规则当文本串中的某个字符跟模式串的某个字符不匹配时我们称文本串中的这个失配字符为坏字符此时模式串需要向右移动移动的位数 坏字符在模式串中的位置 - 坏字符在模式串中最右出现的位置。此外如果坏字符不包含在模式串之中则最右出现位置为-1。好后缀规则当字符失配时后移位数 好后缀在模式串中的位置 - 好后缀在模式串上一次出现的位置且如果好后缀在模式串中没有再次出现则为-1。下面举例说明BM算法。例如给定文本串“HERE IS A SIMPLE EXAMPLE”和模式串“EXAMPLE”现要查找模式串是否在文本串中如果存在返回模式串在文本串中的位置。 1. 首先文本串与模式串头部对齐从尾部开始比较。S与E不匹配。这时S就被称为坏字符bad character即不匹配的字符它对应着模式串的第6位。且S不包含在模式串EXAMPLE之中相当于最右出现位置是-1这意味着可以把模式串后移6-(-1)7位从而直接移到S的后一位。 2. 依然从尾部开始比较发现P与E不匹配所以P是坏字符。但是P包含在模式串EXAMPLE之中。因为“P”这个“坏字符”对应着模式串的第6位从0开始编号且在模式串中的最右出现位置为4所以将模式串后移6-42位两个P对齐。 3. 依次比较得到 “MPLE”匹配称为好后缀good suffix即所有尾部匹配的字符串。注意MPLE、PLE、LE、E都是好后缀。 4. 发现“I”与“A”不匹配“I”是坏字符。如果是根据坏字符规则此时模式串应该后移2-(-1)3位。问题是有没有更优的移法 5. 更优的移法是利用好后缀规则当字符失配时后移位数 好后缀在模式串中的位置 - 好后缀在模式串中上一次出现的位置且如果好后缀在模式串中没有再次出现则为-1。 所有的“好后缀”MPLE、PLE、LE、E之中只有“E”在“EXAMPLE”的头部出现所以后移6-06位。 可以看出“坏字符规则”只能移3位“好后缀规则”可以移6位。每次后移这两个规则之中的较大值。这两个规则的移动位数只与模式串有关与原文本串无关。 6. 继续从尾部开始比较“P”与“E”不匹配因此“P”是“坏字符”根据“坏字符规则”后移 6 - 4 2位。因为是最后一位就失配尚未获得好后缀。 由上可知BM算法不仅效率高而且构思巧妙容易理解。 5. 扩展2Sunday算法 上文中我们已经介绍了KMP算法和BM算法这两个算法在最坏情况下均具有线性的查找时间。但实际上KMP算法并不比最简单的c库函数strstr()快多少而BM算法虽然通常比KMP算法快但BM算法也还不是现有字符串查找算法中最快的算法本文最后再介绍一种比BM算法更快的查找算法即Sunday算法。 Sunday算法由Daniel M.Sunday在1990年提出它的思想跟BM算法很相似
只不过Sunday算法是从前往后匹配在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。 如果该字符没有在模式串中出现则直接跳过即移动位数 匹配串长度 1否则其移动位数 模式串中最右端的该字符到末尾的距离1。下面举个例子说明下Sunday算法。假定现在要在文本串substring searching algorithm中查找模式串search。 1. 刚开始时把模式串与文本串左边对齐 substring searching algorithm search ^ 2. 结果发现在第2个字符处发现不匹配不匹配时关注文本串中参加匹配的最末位字符的下一位字符即标粗的字符 i因为模式串search中并不存在i所以模式串直接跳过一大片向右移动位数 匹配串长度 1 6 1 7从 i 之后的那个字符即字符n开始下一步的匹配如下图
substring searching algorithm search ^ 3. 结果第一个字符就不匹配再看文本串中参加匹配的最末位字符的下一位字符是r它出现在模式串中的倒数第3位于是把模式串向右移动3位r 到模式串末尾的距离 1 2 1 3使两个r对齐如下 substring searching algorithm search ^ 4. 匹配成功。 回顾整个过程我们只移动了两次模式串就找到了匹配位置缘于Sunday算法每一步的移动量都比较大效率很高。完。 6. 参考文献
《算法导论》的第十二章字符串匹配本文中模式串“ABCDABD”的部分图来自于此文http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html本文3.3.7节中有限状态自动机的图由微博网友龚陆安 绘制http://d.pr/i/NEiz北京7月暑假班邹博半小时KMP视频http://www.julyedu.com/video/play/id/5北京7月暑假班邹博第二次课的PPThttp://yun.baidu.com/s/1mgFmw7u理解KMP 的9张PPThttp://weibo.com/1580904460/BeCCYrKz3#_rnd1405957424876详解KMP算法多图http://www.cnblogs.com/yjiyjige/p/3263858.html本文第4部分的BM算法参考自此文http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.htmlhttp://youlvconglin.blog.163.com/blog/static/5232042010530101020857《数据结构 第二版》严蔚敏 吴伟民编著http://blog.csdn.net/v_JULY_v/article/details/6545192http://blog.csdn.net/v_JULY_v/article/details/6111565Sunday算法的原理与实现http://blog.chinaunix.net/uid-22237530-id-1781825.html模式匹配之Sunday算法http://blog.csdn.net/sunnianzhong/article/details/8820123一篇KMP的英文介绍http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm我2014年9月3日在西安电子科大的面试算法讲座视频第36分钟~第94分钟讲KMPhttp://www.julyedu.com/video/play/21一幅图理解KMP next数组的求法http://v.atob.site/kmp-next.html7. 后记 对之前混乱的文章给广大读者带来的困扰表示致歉对重新写就后的本文即将给读者带来的清晰表示欣慰。希望大部分的初学者甚至少部分的非计算机专业读者也能看懂此文。有任何问题欢迎随时批评指正thanks。 July、二零一四年八月二十二日晚九点。
