| 字符串匹配KMP算法详解 | 您所在的位置：网站首页 › 追梦boy › 字符串匹配KMP算法详解 |
字符串匹配KMP算法详解
|
1. 引言
以前看过很多次KMP算法，一直觉得很有用，但都没有搞明白，一方面是网上很少有比较详细的通俗易懂的讲解，另一方面也怪自己没有沉下心来研究。最近在leetcode上又遇见字符串匹配的题目，以此为契机，好好总结一下KMP算法。有何疑问，欢迎评论交流。 2. 暴力匹配算法（传统算法） 假设现在有这样一个问题：有一个文本串S，和一个模式串P，现在要判断S中是否有和P匹配的子串，并查找P在S中的位置，怎么解决呢？ 如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有： 如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；如果匹配失败（即S[i]! = P[j]），令i = i - j + 1，j = 0，即每次匹配失败时，i 回溯到上次开始匹配的下一个位置，j 被置为0。 理清楚了暴力匹配算法的流程及内在的逻辑，咱们可以写出暴力匹配的代码，如下： /** * 暴力破解法 * * @param ss 主串 * @param ps 模式串 * @return 如果找到，返回在主串中第一个字符出现的下标，否则为-1 */ public int violentMatch(String ss, String ps) { char[] s = ss.toCharArray(); char[] p = ps.toCharArray(); int i = 0; // 主串的位置 int j = 0; // 模式串的位置 while (i < s.length && j < p.length) { if (s[i] == p[j]) { //①如果当前字符匹配成功（即s[i]==p[j]），则i++，j++ i++; j++; } else { //②如果失败（即s[i]!=p[j]），令i=i-j+1，j=0 i = i - j + 1; j = 0; } } if (j == p.length) { return i - j; } else { return -1; } } 举个例子，如果给定文本串S“BBC ABCDAB ABCDABCDABDE”，和模式串P“ABCDABD”，现在要拿模式串P去跟文本串S匹配，整个过程如下所示： （1）S[0]为B，P[0]为A，不匹配，故执行第②条指令：“如果失败（即S[i]! = P[j]），令i = i - j + 1，j = 0”，S[1]跟P[0]匹配，相当于模式串要往右移动一位（i=1，j=0） 
（2） S[1]跟P[0]还是不匹配，继续执行第②条指令：“如果失败（即S[i]! = P[j]），令i = i - j + 1，j = 0”，S[2]跟P[0]匹配（i=2，j=0），从而模式串不断的向右移动一位（不断的执行“令i = i - j + 1，j = 0”，i从2变到4，j一直为0） （5） 直到S[10]为空格字符，P[6]为字符D（i=10，j=6），因为不匹配，重新执行第②条指令：“如果失败（即S[i]! = P[j]），令i = i - j + 1，j = 0”，相当于S[5]跟P[0]匹配（i=5，j=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 定义 KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。 下面先直接给出KMP的算法流程（如果感到一点点不适，没关系，坚持下，稍后会有具体步骤及解释）： 假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；如果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 数组各值的含义：若k=next[j]，代表模式串P中当前字符之前的字符串中，最前面的k个字符和j之前的最后k个字符是一样的。 如果用数学公式来表示是这样的： P[0 ~ k-1] == P[j-k ~ j-1] 此也意味着在某个字符匹配失败时，该字符对应的next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置）。如果next [j] 等于0或-1，则跳到模式串的开头字符，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，而不是跳到开头，且具体跳过了k 个字符。 如果用公式证明，是这样的：
当S[i] != P[j]时 有S[i-j ~ i-1] == P[0 ~ j-1] 由P[0 ~ k-1] == P[j-k ~ j-1] 必然：S[i-k ~ i-1] == P[0 ~ k-1] 公式很无聊，能看明白就行了，不需要记住。 这一段只是为了证明我们为什么可以直接将j移动到k而无须再比较前面的k个字符。 转换成代码表示，则是： /** * KMP算法 * * @param ss 主串 * @param ps 模式串 * @return 如果找到，返回在主串中第一个字符出现的下标，否则为-1 */ public static int KMP(String ss, String ps) { |
【本文地址】