一文读懂：通俗易懂的KMP算法详解

我们先提出一个问题给你两个字符串 s 和 pp 的长度不超过 s 的长度且 s 和 p 都不是空的问 s 中是否包含 p例如s“hello, java”, p “java”那么 s 包含 ps“github”, p“ppt”, s 不包含 p能否写出一个程序高效地解决这个问题。我们能容易想到这样的方法设置两个指针i 和 j都初始化为 0我们对比 s 在 i 位置p 在 j 位置的字符。如果 s[i] p[j]那么 i 和 j 都移到下一个位置。否则 j 回退到 0i 回退到 1继续上述过程如果在下一次比较中还是出现了不匹配的字符那么 j 回退到 0i 回退到 2继续……周而复始。直到某一次匹配中如果 j 到达越界位置那么 s 包含 p否则 s 不包含 p。代码如下public class StrContains { public static boolean contains(String s, String p) { int ls s.length(), lp p.length(), i 0, j 0; while(i ls - lp) { int x i; j 0; while(j lp s.charAt(x) p.charAt(j)) { x; j; } if(j lp) return true; i; } return false; } }这样的查找方法在遇到 s “aaaaaaaaaaaaab”p “aab” 这样的情况的时候会使得 p 只有在最后一次匹配的时候才可以得到匹配。假设 s 的长度是 Np 的长度是 M那么显然的最坏情况下时间复杂度就是 O(N∗M)。而 KMP 算法能做到最坏情况下 O(NM) 的时间复杂度。它是怎么做的呢我们一起来看看吧。KMP 算法的计算过程启发的过程上面的暴力方法是基于这样的一个尝试的思路如果 s 中有一个子串和 p 是匹配的因为任何一个子串都有一个开头位置那么这个和 p 匹配的子串当然也有一个开头位置又因为我们不知道哪个开头位置的子串和 p 是匹配的因此我们尝试所有可能的开头。如果我们尝试完所有的开头位置都没有发现一个子串可以和 p 匹配那么 s 中就没有一个子串和匹配即 s 不包含 p反之 s 包含 p。那么这个过程它为什么低效呢我们来看一下 s “aaaaaaaaab” 和 p “aaab” 的匹配过程。当我们发现某一个开头的尝试已经宣告失败的时候此时只能选择下一个开头继续从头开始匹配。那么此时指向 s 的指针会回退之前已经匹配的部分结果完全抛弃从新开始因此这个方法是低效的。如果某一次尝试失败了那么之前已经匹配的部分之前做过的努力能否给我们提供一些帮助加速我们的匹配过程甚至能使得字符串 s 上的指针不回退呢我们调整的时候需要遵循什么原则呢为了便于说明 j 的调整下面我们举一个明显的例子。请看字符串 s “acacab”和字符串 p “acab” 的匹配过程。那么如果已经匹配的部分有多个前缀和后缀是匹配的呢我们怎么选择请看 s “aaaab” 和 p “aaab” 的匹配过程。总结一下此时我们似乎找到了保证 s 指针不回退的时候p 的指针的调整方案即当我们发现某一次匹配失败的时候我们需要找出前面已经匹配部分的 前后缀最大匹配长度假设为 next那么我们只需要把 j 调整为 next继续进行匹配操作即可。next 数组我们在进行真正的匹配之前我们要先计算好每一个元素的 next 值next 值的含义就是当前元素失去匹配的时候它前面部分字符串的前后缀最大匹配长度这个前后缀不包含自己看下面对字符串 “caccacb” 的 next 值的定义过程