KMP模式匹配算法（一）从暴力匹配切入

xfee 发布于2019-08-22 10:37 / 876人阅读

摘要：朴素的模式匹配算法这种算法又被称为暴力匹配算法。如果匹配失败，则回溯到主串的下一个位置重新逐位匹配。当然，在匹配算法中不同的输入会有不同的复杂度，最好的情况就是一开始就匹配成功。切入结束，下篇详解匹配算法

最近在看关于算法方面的，正好看到关于KMP算法相关的部分，这里就做一个总结。
假设我们有这样的一个主串

S = "googlgomglegoogle"

和一个子串

C = "google"

我们现在有这样的一个需求那就是要在主串S中找到子串C出现的位置。可能马上会有很聪明的同学提出来，可以用indexOf方法啊。那我只能说这个方法不算。。。

朴素的模式匹配算法

这种算法又被称为暴力匹配算法。
也就是逐位匹配，假设主串的位置i子串的位置j，如果有位置j和位置i的字符相等的话，i++, j++。如果匹配失败，则回溯到主串的下一个位置重新逐位匹配。好的，我知道你肯定没有听明白，还是直接上代码好了。

var S = "googlgomglegoogle"
var C = "google"

var sPositon = 0
function violence1() {
  for (var i in C) {
    if (C.charAt(i) !== S.charAt(sPositon)) {
      sPositon += 1
      violence1()
    }
  }
  console.log(sPositon)
}

violence1()

然后就悲剧了

for (var i in C) {
           ^

RangeError: Maximum call stack size exceeded

超过最大调用堆栈大小, 递归没有终止会永远的循环下去，内存已爆。所以递归套循环还是需要谨慎。
好吧，那这样我们就改变一下。下面我写了两种实现方式

// 暴力匹配1
for (let i = 0; i < mainStr.length; i += 1) {
  for (let j = 0; j < searchStr.length; j += 1) {
    if (searchStr[j] !== mainStr[i + j]) {
      break
    } else if (searchStr[searchStr.length - 1] === mainStr[i + j]) {
      console.log(i)
    }
  }
}

// 暴力匹配2

let i = 0
let j = 0
while (i < mainStr.length && j < searchStr.length) {
  if (mainStr[i] === searchStr[j]) {
    i += 1
    j += 1
  } else {
    i += 1
    j = 0
  }
}
if (j === searchStr.length) {
  console.log(i - j)
} else {
  console.log("-1")
}

输出结果是11，还是很符合我们预期的效果的。那现在我们来分析一下这个算法的复杂度怎么样。
当然，在匹配算法中不同的输入会有不同的复杂度，最好的情况就是一开始就匹配成功。比如

S = "googlestwo"
C = "google"

此时的时间复杂度是O(1)
稍微差一点的情况，就是前几位的每一位都和子串的第一位不匹配，例如

S = "abcderfgoogle"
C = "google"

此时的时间复杂度为O(m + n), m为主串的长度，n为子串的长度。
最后我们分析最极端也就是最坏的情况也就是每一次不成功的匹配都发生在子串的最后一位，例如

S = "googlgooglgooglgooglgooglgooglgooglgooglgooglgooglgooglgoogle"
C = "google"

你说这气人不气人，就像炸金花的时候前两张都是红桃，最后一张突然蹦出个梅花，而且每把都这样。。。
此时的时间复杂度为O((n-m+1)m)
很显然这样的运行效率是十分低的。所以我们需要更加高效的算法－KMP模式匹配算法。
切入结束，下篇详解KMP匹配算法

云服务器 GPU云服务器字符串的模式匹配算法匹配模式模式匹配模式匹配图像识别

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/90955.html

[算法总结] 搞定 BAT 面试——几道常见的子符串算法题

摘要：第一种方法常规方法。如果不存在公共前缀，返回空字符串。注意假设字符串的长度不会超过。说明本题中，我们将空字符串定义为有效的回文串。示例输入输出一个可能的最长回文子序列为。数值为或者字符串不是一个合法的数值则返回。说明本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站点：https://www.weiweiblog.c...

chanjarster 2019-08-19 11:07 评论0 收藏0
结合kmp算法的匹配动画浅析其基本思想

摘要：写在最前本次分享一下通过实现算法的动画效果来试图展示的基本思路。算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。本次主要通过动画演示的方式展现朴素算法与算法对比过程的异同从而试图理解的基本思路。写在最前本次分享一下通过实现kmp算法的动画效果来试图展示kmp的基本思路。欢迎关注我的博客，不定期更新中—— 前置概念字符串匹配字符串匹配是计算...

wpw 2019-08-22 14:51 评论0 收藏0
字符串匹配算法之KMP模式

摘要：字符串的普通模式匹配普通模式匹配的原理不进行说明了，简单来说就是两个字符串的每个字符依次进行匹配。这篇文章主要是介绍KMP模式匹配算法，在正式介绍KMP之前我们先看一下普通模式匹配，由普通模式匹配在进一步的推导KMP模式会更容易理解。字符串的普通模式匹配普通模式匹配的原理不进行说明了，简单来说就是两个字符串的每个字符依次进行匹配。 public int match(String ...

NeverSayNever 2019-08-16 14:03 评论0 收藏0
数据结构-BF算法及KMP算法

摘要：算法代码复杂度最坏情况的时间复杂度。算法简单记忆分为两步模式串扫描，生成数组，。算法对算法的回溯问题进行了改进，在整个匹配过程中对主串仅需从头至尾扫描一遍。在定义函数时在参数前加上改为引传递。一般情况为值传递，对象除外。 BF算法代码复杂度最坏情况的时间复杂度O(m*n)。m为模式串长度。n为目标串长度。 KMP算法代码时间复杂度时间复杂度为O(m+n)。m为模式串长度...

jollywing 2019-06-27 16:20 评论0 收藏0