KMP算法讲解之――不需要公式,就能理解KMP算法

1、KMP算法，20XX。XX.XX，报告者：XXX，KMP算法，1。KMP背景简介，3 .KMP核心跳转表next，2 .简单匹配到KMP，4 .next计算得出f (j)，KMP算法，1 .在KMP背景介绍、文本编辑中经常查找特定的字符或模式。例如，HTTP协议的字节流具有各种关键字节流字段，需要模式匹配算法来解释HTTP数据。结果是字符串匹配问题。KMP算法是Knuth、Morris和Pratt联合建议的模式匹配算法，它可以在联机时间内完成匹配查找，而不会影响任何模式和目标序列，是一种非常好的模式匹配算法。KMP算法，ii。目标字符串(target)t=b a b c a b c a b c

2、 a b c a b c a b c a c a b c a b c a b c模式字符串(pattern)p=a b c a b c a b c a b。如何更有生产力？朴素匹配，我们查找16号，KMP算法查找6号匹配模式字符串，朴素匹配时间复杂度o (m * n)。KMP的时间复杂度为O(n)。KMP算法，3 .KMP算法内核移动表next，实际上，模式字符串通常包含特定的信息前缀。对于模式字符串，前缀字符串也可以是模式字符串(称为“包含前缀”问题)中的非前缀子字符串。那一次要跑多远？这与跳转表next保存的值相关。例如，模式字符串a b c a b c a b例如，名为a b c a的四

3、个字符是模式字符串中的子字符串a b c (a b c a) c a b，因此，在将匹配到第八个字符的目标字符串与模式字符串匹配时，如果不匹配到第八个字符，则目标字符串中当前字符之前的四个字符也是指目标字符串之前的四个字符。与模式字符串的前四个字符相同，因此当模式字符串向后移动时，通过将模式字符串的第五个字符直接与当前字符对齐来执行比较，模式字符串可以一次向前跳跃多个字符。KMP算法，3 .KMP算法核心跳转表next，模式字符串p=a b c a b c a b，跳转表：KMP算法，3。KMP算法核心跳转表next，KMP匹配步骤3示例：时，pattern字符串中的第一个字符与target6

4、对齐。将目标字符串从6依次匹配到3，然后为target13=a，pattern8=c，如果匹配失败，则为next8=5，因此将模式字符串移动到8-next8=3个字符之后，将pattern5与target13对齐，然后从target13反向匹配，再执行操作。直到找到图案字符串或遍历整个目标字符串时，目标字符串中的输入字符才会在图案字符串中反向移动。KMP算法，4 .next的计算引入了f(j)，跳台next如何计算？如何以更少的成本计算呢？图案字符串的第j个字符patternnj，f(j)介绍了概念f(j)，即满足构成patter n1k-1=patter nnj-(k-1)j-1(k j)的

5、所有k的最大值F(j)=k k最小k为2，因此指定f (1)=0。如果没有前缀，则f(j)=1，图案字符串p=a b c a c a b的f(j)计算如下：KMP算法，4 .next的计算引入了f(j)，f(j)语义。对于图案字符串中的第j个字符patternnj，f(j)是为pattern 1k-1=patternnj-(k-1)j-1(k j)设置的所有k的最大值。F(j)=k，例如，如果11位模式字符串为a b a b c d a b a b g，则f(11)=5！=3 .如何理解k最大值？通过上图，我们很容易看出，k越小，跳跃的速度越大，符合条件的匹配结果跳跃的可能性就越大，所以在保证

6、快速算法的同时，必须保证准确性！KMP算法，4 .next的计算必须引入f(j)，以pattern8为例，说明f(j)和nextj之间的关系，匹配才会失败。F(8)=5，pattern14=pattern47，此时我们有pattern8: 1。必须集中精力处理pattern8！您可以将targetn与patternnf (8)=pattern5对齐，然后反向匹配8=f (8)，因为只有与pattern5匹配时target n失败。KMP算法，4 .next的计算引入f (j)，2 .pattern8=pattern5表示targetn-4n，因为targetn与pattern8不匹配！=pat

7、tern48，将targetn与pattern5对齐时，targetn-4n可能也不等于pattern15。这时我们必须集中在f(5)上。KMP算法，4 .next的计算结果为f (j)，2 .pattern8=pattern5 f(5)=2表示pattern1=pattern4。这是pattern14=pattern47，因此pattern4=pattern7=pattern1。现在，我们将比较pattern8和pattern2。2.1如果pattern8！=pattern2将target2与pattern2对齐，然后比较两个项目是否相同。此时，next 8=nexttf (8)=next 5=f (5)。KMP算法，4 .next的计算引入了f (j)，如果2.2 pattern8=patternf(2)，还需要查看patternnf (2)，直到回到模式字符串头。KMP算法，4 .next的计算引入了f(j)，通过以上分析，可以总结出基于f(j)查找nextj的递归公式：patternj！=patt