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

xfee 發布于2019-08-22 10:37 / 888人閱讀

摘要：樸素的模式匹配算法這種算法又被稱為暴力匹配算法。如果匹配失敗，則回溯到主串的下一個位置重新逐位匹配。當然，在匹配算法中不同的輸入會有不同的復雜度，最好的情況就是一開始就匹配成功。切入結束，下篇詳解匹配算法

最近在看關于算法方面的，正好看到關于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云服務器字符串的模式匹配算法匹配模式模式匹配模式匹配圖像識別

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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