成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

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

xfee / 965人閱讀

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

最近在看關(guān)于算法方面的，正好看到關(guān)于KMP算法相關(guān)的部分，這里就做一個(gè)總結(jié)。
假設(shè)我們有這樣的一個(gè)主串

S = "googlgomglegoogle"

和一個(gè)子串

C = "google"

我們現(xiàn)在有這樣的一個(gè)需求那就是要在主串S中找到子串C出現(xiàn)的位置?？赡荞R上會有很聰明的同學(xué)提出來，可以用indexOf方法啊。那我只能說這個(gè)方法不算。。。

樸素的模式匹配算法

這種算法又被稱為暴力匹配算法。
也就是逐位匹配，假設(shè)主串的位置i子串的位置j，如果有位置j和位置i的字符相等的話，i++, j++。如果匹配失敗，則回溯到主串的下一個(gè)位置重新逐位匹配。好的，我知道你肯定沒有聽明白，還是直接上代碼好了。

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

超過最大調(diào)用堆棧大小, 遞歸沒有終止會永遠(yuǎn)的循環(huán)下去，內(nèi)存已爆。所以遞歸套循環(huán)還是需要謹(jǐn)慎。
好吧，那這樣我們就改變一下。下面我寫了兩種實(shí)現(xiàn)方式

// 暴力匹配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")
}

輸出結(jié)果是11，還是很符合我們預(yù)期的效果的。那現(xiàn)在我們來分析一下這個(gè)算法的復(fù)雜度怎么樣。
當(dāng)然，在匹配算法中不同的輸入會有不同的復(fù)雜度，最好的情況就是一開始就匹配成功。比如

S = "googlestwo"
C = "google"

此時(shí)的時(shí)間復(fù)雜度是O(1)
稍微差一點(diǎn)的情況，就是前幾位的每一位都和子串的第一位不匹配，例如

S = "abcderfgoogle"
C = "google"

此時(shí)的時(shí)間復(fù)雜度為O(m + n), m為主串的長度，n為子串的長度。
最后我們分析最極端也就是最壞的情況也就是每一次不成功的匹配都發(fā)生在子串的最后一位，例如

S = "googlgooglgooglgooglgooglgooglgooglgooglgooglgooglgooglgoogle"
C = "google"

你說這氣人不氣人，就像炸金花的時(shí)候前兩張都是紅桃，最后一張突然蹦出個(gè)梅花，而且每把都這樣。。。
此時(shí)的時(shí)間復(fù)雜度為O((n-m+1)m)
很顯然這樣的運(yùn)行效率是十分低的。所以我們需要更加高效的算法－KMP模式匹配算法。
切入結(jié)束，下篇詳解KMP匹配算法

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/90955.html

相關(guān)文章

  • [算法總結(jié)] 搞定 BAT 面試——幾道常見的子符串算法題

    摘要：第一種方法常規(guī)方法。如果不存在公共前綴，返回空字符串。注意假設(shè)字符串的長度不會超過。說明本題中，我們將空字符串定義為有效的回文串。示例輸入輸出一個(gè)可能的最長回文子序列為。數(shù)值為或者字符串不是一個(gè)合法的數(shù)值則返回。 說明 本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站點(diǎn)：https://www.weiweiblog.c...

    chanjarster 評論0 收藏0

  • 結(jié)合kmp算法的匹配動畫淺析其基本思想

    摘要：寫在最前本次分享一下通過實(shí)現(xiàn)算法的動畫效果來試圖展示的基本思路。算法的關(guān)鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。本次主要通過動畫演示的方式展現(xiàn)樸素算法與算法對比過程的異同從而試圖理解的基本思路。 寫在最前 本次分享一下通過實(shí)現(xiàn)kmp算法的動畫效果來試圖展示kmp的基本思路。 歡迎關(guān)注我的博客，不定期更新中—— 前置概念 字符串匹配 字符串匹配是計(jì)算...

    wpw 評論0 收藏0

  • 字符串匹配算法之KMP模式

    摘要：字符串的普通模式匹配普通模式匹配的原理不進(jìn)行說明了，簡單來說就是兩個(gè)字符串的每個(gè)字符依次進(jìn)行匹配。 這篇文章主要是介紹KMP模式匹配算法，在正式介紹KMP之前我們先看一下普通模式匹配，由普通模式匹配在進(jìn)一步的推導(dǎo)KMP模式會更容易理解。 字符串的普通模式匹配 普通模式匹配的原理不進(jìn)行說明了，簡單來說就是兩個(gè)字符串的每個(gè)字符依次進(jìn)行匹配。 public int match(String ...

    NeverSayNever 評論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)-BF算法及KMP算法

    摘要：算法代碼復(fù)雜度最壞情況的時(shí)間復(fù)雜度。算法簡單記憶分為兩步模式串掃描，生成數(shù)組，。算法對算法的回溯問題進(jìn)行了改進(jìn)，在整個(gè)匹配過程中對主串僅需從頭至尾掃描一遍。在定義函數(shù)時(shí)在參數(shù)前加上改為引傳遞。一般情況為值傳遞，對象除外。 BF算法 代碼 復(fù)雜度 最壞情況的時(shí)間復(fù)雜度O(m*n)。m為模式串長度。n為目標(biāo)串長度。 KMP算法 代碼 時(shí)間復(fù)雜度 時(shí)間復(fù)雜度為O(m+n)。m為模式串長度...

    jollywing 評論0 收藏0

發(fā)表評論

0條評論

xfee

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<