搜索
KMP算法20XX.XX.XX汇报人：XXX汇报提纲KMP算法一.KMP背景介绍三.KMP核心——跳转表next[]二.由朴素匹配到KMP四.next[]的计算——引入f(j)KMP算法一.KMP背景介绍在文本编辑中，我们经常要在一段文本中某个特定的位置找出某个特定的字符或模式。再比如，在HTTP协议里的字节流,有各种关键的字节流字段,对HTTP数据进行解释就需要用到模式匹配算法。由此，便产生了字符串的匹配问题。KMP算法是由Knuth，Morris，Pratt三人共同提出的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，是一个非常优秀的模式匹配算法。KMP算法二.由朴素匹配到KMP假设有目标字符串(Target)T=babcbabcabcaabcabcabcacabc，我们要在其中找到模式字符串（Pattern）P=abcabcacab。如何做更为高效呢？由朴素匹配，我们要做16次，而KMP算法仅匹配了6次就找到了模式字符串朴素匹配的时间复杂度为O(m*n)；KMP的时间复杂度为O(n)。KMP算法三.KMP算法核心——跳转表next[]其实，模式串往往含有一定的信息——前缀包含。对于模式串而言，其前缀字符串，有可能也是模式串中的非前缀子串，这个问题我称之为前缀包含问题。那么每次要跳跃多少呢？这与跳转表next[]存储的数值相关。以模式串abcabcacab为例，其前缀的4个字符abca，正好也是模式串的一个子串abc(abca)cab，所以当目标串与模式串执行匹配的过程中，如果直到第8个字符才匹配失败，同时也意味着目标串当前字符之前的4个字符，与模式串的前4个字符是相同的，所以当模式串向后移动的时候，可以直接将模式串的第5个字符与当前字符对齐，执行比较，这样就实现了模式串一次性向前跳跃多个字符。KMP算法三.KMP算法核心——跳转表next[]模式字符串P=abcabcacab，其跳转表为：KMP算法三.KMP算法核心——跳转表next[]我们以KMP匹配的第3步为例:此时pattern串的第1个字母与target[6]对齐，从6向后依次匹配目标串，到target[13]时发现target[13]='a'，而pattern[8]='c'，匹配失败，此时next[8]=5，所以将模式串向后移动8-next[8]=3个字符，将pattern[5]与target[13]对齐，然后由target[13]依次向后执行匹配操作。在整个匹配过程中，无论模式串如何向后滑动，目标串的输入字符都不会回溯，直到找到模式串，或者遍历整个目标串都没有发现匹配模式为止。KMP算法四.next[]的计算——引入f(j)跳转表next[]是如何计算的呢？以及怎样以较小的代价计算?这里我们引入一个概念f(j)，其含义是，对于模式串的第j个字符pattern[j]，f(j)是所有满足使pattern[1···k-1]=pattern[j-(k-1)···j-1](kj)成立的k的最大值。f(j)=k我们可以看出k最小为2，因此，规定f(1)=0；不存在前缀包含时，f(j)=1模式字符串P=abcabcacab的f(j)计算结果如下：KMP算法四.next[]的计算——引入f(j)f(j)含义：对于模式串的第j个字符pattern[j]，f(j)是所有满足使pattern[1···k-1]=pattern[j-(k-1)···j-1](kj)成立的k的最大值。f(j)=k比如，假设一个11位模式字符串为ababcdababg，则f(11)=5!=3。如何理解取K最大值呢？通过上图，我们不难看出，k越小，跳跃的步伐越大，很可能会把满足条件的匹配结果跳过去，因此我们在保证算法快速的同时，还要保证准确！KMP算法四.next[]的计算——引入f(j)为了说明f(j)和next[j]之间的关系，我们以pattern[8]为例，假如匹配到pattern[8]才匹配失败。f(8)=5,pattern[1···4]=pattern[4···7]，此时我们需要关注pattern[8]：1.如果pattern[8]!=pattern[5]因为在匹配到pattern[8]时才失败，此时就可以将输入字符target[n]与pattern[f(8)]=pattern[5]对齐，再向后依次执行匹配，所以此时的next[8]=f(8)。KMP算法四.next[]的计算——引入f(j)2.如果pattern[8]=pattern[5]那么pattern[1···5]=pattern[4···8]，因为target[n]与pattern[8]匹配失败，那么也意味着target[n-4···n]!=pattern[4···8]，那么将target[n]与pattern[5]对齐，target[n-4···n]也必然不等于pattern[1···5]。此时我们需要关注f(5)。KMP算法四.next[]的计算——引入f(j)2.如果pattern[8]=pattern[5]f(5)=2，这意味着pattern[1]=pattern[4]，因为pattern[1···4]=pattern[4···7]，所以pattern[4]=pattern[7]=pattern[1],此时我们再来比较pattern[8]和pattern[2]。2.1如果pattern[8]!=pattern[2]就可以将target[2]与pattern[2]对齐，然后比较二者是否相等，此时next[8]=next[f(8)]=next[5]=f(5)。KMP算法四.next[]的计算——引入f(j)2.2如果pattern[8]=pattern[2]那么还需要考察pattern[f(2)]，……直到回溯到模式串头部为止。KMP算法四.next[]的计算——引入f(j)由以上分析，我们可以归纳出根据f(j)求next[j]的递推公式：如果pattern[j]!=pattern[f(j)]，next[j]=f(j);如果pattern[j]=pattern[f(j)]，next[j]=next[f(j)];KMP算法四.next[]的计算——引入f(j)谢谢学号：XXXXXXXX汇报人：XXX班级：XXXXX